题目链接:传送门
题目大意:略
题目思路:其实问了学长才会做这个题，准确说细节处理都没问题，主要是方向没对(说了跟没说一样)，这个题目我们观察数据有1e5组测例，单组测例的单个数据最大1e5
限时1s，所以时间复杂度要求很高。其实有想过二分这种思想但是不知道怎么二分。
我们观察三种礼包，每种礼包其实都可以拆成两部分（1个U盘1个鼠标+X）那么我们可以想到将每件礼品都拆为两部分，然后我们对于U盘和鼠标的数目进行二分，
也就是二分答案。而判断二分值是否合理的依据是我们枚举的U盘和鼠标数<=X的数目。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 2000005 #define maxn 100005 typedef pair<int,int> PII; typedef long long LL; int a[5],x1,x2,x3; int solve(int xx){ int temp; a[1]=x1-xx;a[2]=x2-xx;a[3]=x3; if(a[1]<0||a[2]<0)return 0; sort(a+1,a+4);///这里是为了满足题目中要求相邻的礼包不能相同 if(a[1]+a[2]<a[3])temp=(a[1]+a[2])*2+1; else temp=a[1]+a[2]+a[3]; if(xx<=temp)return 1; return 0; } int main(){ int i,j,group,temp,ans; scanf("%d",&group); while(group--){ scanf("%d%d%d",&x1,&x2,&x3); temp=x1+x2+x3; int l=0,r=temp,mid; while(l<=r){ mid=l+r>>1; ///枚举拆出来的U盘鼠标 if(solve(mid)){ l=mid+1; ans=mid; } else r=mid-1; } printf("%d ",ans); } return 0; }