这题！！！
得先把题目看清。
看清了吗？那我开写了。
首先得把数据处理成我们喜欢的样子，也就是俩石头间的距离。
然后我们可以确定最终答案的范围，也就是0到L。
有点感觉了吗？这就是经典的二分答案类题目。准确一点说，是二分和贪心的结合。思路为用二分寻找可能的最短跳跃距离，再看它是否符合要求，即当每两块石头之间距离刚刚超过它时，所需搬走的石头数小于等于组委会至多移走的数量。
#include<bits/stdc++.h>usingnamespacestd;intlen,n,m;intb[50010];boolcheck(intx){intcnt=0;for(inti=0;i<=n;i++){intsum=b[i];while(i<=n&&sum<x)//这里跳出循环时，sum刚好大于x{i++;sum+=b[i];cnt++;}}returncnt<=m;}intmain(){cin>>len>>n>>m;inttemp=0;for(inti=0;i<n;i++){intnow;cin>>now;b[i]=now-temp;temp=now;}b[n]=len-temp;intl=0,r=len;intans;while(l<=r){intmid=(l+r)/2;if(check(mid)){ans=mid;l=mid+1;//尝试更大的距离，找最优解}else{r=mid-1;//不符合条件，缩小距离}}cout<<ans;return0;}
这题和上体解法类似。
幸福值范围：
0–全部和。
二分时判断是否合法的check函数思路：
1至d天每天吃的巧克力幸福值相加要刚好大于待定值，如果巧克力吃完了但幸福值依然低于待定值，则该值不合法。
这里有两个坑。一是有的情况合法，还多出了巧克力，需要把剩余巧克力全部放进最后一天。二是当找到最优解时，查找可能未结束，后面调用check会覆盖正确值，需另外存储。
完整代码：
#include<bits/stdc++.h>usingnamespacestd;intn,d;inta[50010],b[50010],c[50010];boolcheck(longlongx){longlongcur=0,s=0;for(inti=1;i<=d;i++){cur/=2;while(cur<x&&s<n){s++;cur+=a[s];b[s]=i;}if(cur<x){returnfalse;}}for(inti=s+1;i<=n;i++){b[i]=d;}//坑一returntrue;}intmain(){cin>>n>>d;longlongsum=0;for(inti=1;i<=n;i++){cin>>a[i];sum+=a[i];}longlongl=0,r=sum,ans=0;while(l<=r){longlongmid=(l+r)/2;if(check(mid)){ans=mid;copy(begin(b),end(b),begin(c));//坑二l=mid+1;}else{r=mid-1;}}cout<<ans<<endl;for(inti=1;i<=n;i++){cout<<c[i]<<endl;}return0;}本题核心为贪心模拟 + 前缀和枚举最优分配，分为两步核心操作：
- 预处理承载数量：分别模拟国内、国际航班的停靠过程，统计出：分配kkk个廊桥时，对应区域最多可停靠的飞机数量。
- 枚举最优分配方案：枚举国内廊桥的分配数量iii（（（0≤i≤n0\le i\le n0≤i≤n），剩余n−i），剩余 n-i），剩余n−i个廊桥分配给国际区，取两者停靠总数的最大值即为答案。
模拟流程：
- 将当前区域所有航班按抵达时间升序排序；
- 初始时所有廊桥均为空闲，入空闲堆；
- 遍历每一架航班：先清空占用堆中离开时间≤当前航班抵达时间的廊桥，将其回收至空闲堆；
- 若存在空闲廊桥，分配最小编号廊桥，更新该廊桥的承载计数，并将廊桥标记为占用；无空闲则该航班停靠远机位。
法一
全部枚举出方案。
45分：
#include<bits/stdc++.h>usingnamespacestd;intn,m1,m2;intjs(vector<pair<int,int>>&v,intk){if(k==0)return0;priority_queue<int,vector<int>,greater<int>>q;intres=0;for(inti=0;i<v.size();i++){intl=v[i].first;intr=v[i].second;while(!q.empty()&&q.top()<=l)q.pop();if(q.size()<k){q.push(r);res++;}}returnres;}intmain(){cin>>n>>m1>>m2;vector<pair<int,int>>d(m1);vector<pair<int,int>>g(m2);for(inti=0;i<m1;i++)cin>>d[i].first>>d[i].second;for(inti=0;i<m2;i++)cin>>g[i].first>>g[i].second;sort(d.begin(),d.end());sort(g.begin(),g.end());intans=0;for(inti=0;i<=n;i++){intcnt_d=js(d,i);intcnt_g=js(g,n-i);ans=max(ans,cnt_d+cnt_g);}cout<<ans;return0;}法二
我们知道，分配更少廊桥数时可停靠的飞机在分配到更多廊桥数时一定也能停靠。可以参考下面这个表：
所以把模拟流程的函数改一下，最后返回每个廊桥停的飞机数。而飞机总数是前缀和所有此前飞机再加上新增飞机数（即目前最后一个廊桥所装飞机）。
#include<bits/stdc++.h>usingnamespacestd;intn,m1,m2;vector<int>js(vector<pair<int,int>>&v,intk){vector<int>res(k+1,0);priority_queue<int,vector<int>,greater<int>>q_id;//空闲廊桥编号priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>b_id;//廊桥的编号和离开时间for(inti=1;i<=k;i++){q_id.push(i);}for(inti=0;i<v.size();i++){intl=v[i].first;intr=v[i].second;while(!b_id.empty()&&b_id.top().first<=l){intid=b_id.top().second;b_id.pop();q_id.push(id);}if(q_id.empty())continue;intid=q_id.top();q_id.pop();res[id]++;b_id.push({r,id});}returnres;}intmain(){cin>>n>>m1>>m2;vector<pair<int,int>>d(m1);vector<pair<int,int>>g(m2);for(inti=0;i<m1;i++)cin>>d[i].first>>d[i].second;for(inti=0;i<m2;i++)cin>>g[i].first>>g[i].second;sort(d.begin(),d.end());sort(g.begin(),g.end());intans=0;vector<int>cd=js(d,n);vector<int>cg=js(g,n);vector<int>pd(n+1,0),pg(n+1,0);for(inti=0;i<=n;i++){pd[i]=pd[i-1]+cd[i];pg[i]=pg[i-1]+cg[i];}for(inti=0;i<=n;i++)ans=max(ans,pd[i]+pg[n-i]);cout<<ans;return0;}
假设n=1，所以一共有9×5(拨一个拨圈)+9×4(拨两个拨圈)=81种。直接输出81可以得高达30分哦！
正解
这道题枚举所有情况来讨论可以做对。
如果按每一位不同情况设置就会有五层循环，显然不可取。所以得按数字加一再数位分离得到。但注意i从100000开始，到199999结束。如果是00000数位分离结果会是0。
然后就是判断这个数是否可取。可以用一个循环遍历所有状态，在与之对比。若有2位以上或0位不同就不合法；若只有一位则必定合法；若有两位就得看是否相邻，转动幅度是否一样。
#include<bits/stdc++.h>usingnamespacestd;intn,a[6],b[10][5],ans=0;boolcheck(inta[],intb[][5]){for(inti=0;i<n;i++){ints=0;for(intj=0;j<5;j++){if(b[i][j]!=a[j])s++;}if(s>2||s==0)return0;if(s==1)continue;for(intj=0;j<5;j++){if(b[i][j]!=a[j]){if(b[i][j+1]==a[j+1])return0;elseif((b[i][j]-a[j]+10)%10==(b[i][j+1]-a[j+1]+10)%10){break;}elsereturn0;}}}returntrue;}intmain(){cin>>n;for(inti=0;i<n;i++){for(intj=0;j<=4;j++){cin>>b[i][j];}}for(inti=100000;i<=199999;i++){intx=i;for(intj=4;j>=0;j--){a[j]=x%10;x/=10;}if(check(a,b)){ans++;}}cout<<ans;return0;}
一道简单的模拟题。
两个变量，一个存需要多少天，用一个while，让苹果数每天自减1/3（向上取整）；
另一个存第n个需要多少天，用一个while，让n每天自减1/3（向上取整），当n%3==1时break。
#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,x;cin>>n;x=n;intcnt=0,day=0;while(x){x=x-ceil(x/3.0);cnt++;}while(true){day++;if(n%3==1)break;n=n-ceil(n/3.0);}cout<<cnt<<" "<<day;return0;}
