排序+dfs+简单剪枝
幸运的袋子_牛客题霸_牛客网
思路：
对于任意两个正整数 a,b 如果满足 a+b>a b ，则必有 一个数为 1. 可用数论证明：设 a=1+x,b=1+y ，则 1+x+1+y>(1+x) (1+y) ， ---> 1>x y ，则 x ， y 必有一个为 0 ，即 a,b 有一个为 1.
将球按标号升序排序。每次从小到大选择，当选择到a1,a2,...,ak-1时满足给定条件，而再增加选择ak时不满足条件（ak必然大于等于max(a1,a2,...,ak-1)），继续向后选择更大的数，必然无法满足！此时不必再继续向后搜索。
如果有多个1，即当k=1时，sum(1)>pi(1)不满足，但下一个元素仍为1，则可以满足1+1>1*1， 所以要判断当前ak是否等于1，如果等于1，虽然不能满足，组合的个数不能增加，但是继续向后搜索，仍然有满足条件的可能.
对于重复数字，组合只能算一个，要去重
#include <iostream> #include<algorithm> using namespace std; int x[1010];//所有球 int n; //总数 int ans; //幸运袋子数 int sum,mul; void dfs(int pos) //pos当前搜索的位置 { for(int i=pos;i<n;i++)//循环，搜索以位置i开始所有可能的组合 { sum+=x[i]; mul*=x[i]; if(sum>mul) { ans++; dfs(i+1); } //k=1时，sum(1)>pi(1)不满足，但下一个元素仍为1，则可以满足1+1>1*1 else if(x[i]==1) dfs(i+1); else { sum-=x[i]; mul/=x[i]; break; } //要搜索下一个位置之前，首先恢复sum和multi(回溯) sum-=x[i]; mul/=x[i]; //数字相同的球，没有什么区别，都只能算一个组合，所以直接跳过 while(i<n-1&&x[i]==x[i+1]) i++; } } int main() { while(cin>>n){ mul=1; for(int i=0;i<n;i++) cin>>x[i]; sort(x,x+n); dfs(0); cout<<ans<<endl; } return 0; }
贪心+模拟
思路： （别被题目解释误导了！）
要想能够让左右手套至少有一副配对,我们可以先把左手手套每种都至少拿一只,然后再随便拿一只右手手套就可以成功配对 ，左手套每种拿一只同理。
对于非0递增序列a1,a2...an，要想最终取值覆盖每一个种类 n = sum(a1...an) - a1 + 1（也就是总数减去最小值之后加一）
最小数量leftsum = 左边数量和 - 左边最小值 + 1
rightsum = 右边数量和 - 右边的最小值 + 1
而对于有0存在的，则需要做累加， 保证覆盖每一种颜色
class Gloves { public: int findMinimum(int n, vector<int> left, vector<int> right) { int leftsum=0,lmin=INT_MAX; int rightsum=0,rmin=INT_MAX; int sum=0; for(int i=0;i<n;i++) { if(left[i]*right[i]==0) sum+=left[i]+right[i];//对于有0，则不可能配对，累加保底 else //找到最小值和总和 { leftsum+=left[i]; rightsum+=right[i]; lmin=min(lmin,left[i]);//更新左右手套的最小数量 rmin=min(rmin,right[i]); } } //对左右手套覆盖所以颜色的拿法取min+0存在保底数+加一表示顺便拿一个手套即可配对 return sum+min(leftsum-lmin+1,rightsum-rmin+1)+1; } };
