★ FEATURED ARTICLE 这题得先把题目看清。看清了吗那我开写了。首先得把数据处理成我们喜欢的样子也就是俩石头间的距离。然后我们可以确定最终答案的范围也就是0到L。有点感觉了吗这就是经典的二分答案类题目。准确一点说是二分和贪心的结合。思路为用二分寻找可能的最短跳跃距离再看它是否符合要求即当每两块石头之间距离刚刚超过它时所需搬走的石头数小于等于组委会至多移走的数量。#includebits/stdc.husingnamespacestd;intlen,n,m;intb[50010];boolcheck(intx){intcnt0;for(inti0;in;i){intsumb[i];while(insumx)//这里跳出循环时sum刚好大于x{i;sumb[i];cnt;}}returncntm;}intmain(){cinlennm;inttemp0;for(inti0;in;i){intnow;cinnow;b[i]now-temp;tempnow;}b[n]len-temp;intl0,rlen;intans;while(lr){intmid(lr)/2;if(check(mid)){ansmid;lmid1;//尝试更大的距离找最优解}else{rmid-1;//不符合条件缩小距离}}coutans;return0;}这题和上体解法类似。幸福值范围0–全部和。二分时判断是否合法的check函数思路1至d天每天吃的巧克力幸福值相加要刚好大于待定值如果巧克力吃完了但幸福值依然低于待定值则该值不合法。这里有两个坑。一是有的情况合法还多出了巧克力需要把剩余巧克力全部放进最后一天。二是当找到最优解时查找可能未结束后面调用check会覆盖正确值需另外存储。完整代码#includebits/stdc.husingnamespacestd;intn,d;inta[50010],b[50010],c[50010];boolcheck(longlongx){longlongcur0,s0;for(inti1;id;i){cur/2;while(curxsn){s;cura[s];b[s]i;}if(curx){returnfalse;}}for(intis1;in;i){b[i]d;}//坑一returntrue;}intmain(){cinnd;longlongsum0;for(inti1;in;i){cina[i];suma[i];}longlongl0,rsum,ans0;while(lr){longlongmid(lr)/2;if(check(mid)){ansmid;copy(begin(b),end(b),begin(c));//坑二lmid1;}else{rmid-1;}}coutansendl;for(inti1;in;i){coutc[i]endl;}return0;}本题核心为贪心模拟 前缀和枚举最优分配分为两步核心操作预处理承载数量分别模拟国内、国际航班的停靠过程统计出分配kkk个廊桥时对应区域最多可停靠的飞机数量。枚举最优分配方案枚举国内廊桥的分配数量iii0≤i≤n0\le i\le n0≤i≤n剩余n−i剩余 n-i剩余n−i个廊桥分配给国际区取两者停靠总数的最大值即为答案。模拟流程将当前区域所有航班按抵达时间升序排序初始时所有廊桥均为空闲入空闲堆遍历每一架航班先清空占用堆中离开时间≤当前航班抵达时间的廊桥将其回收至空闲堆若存在空闲廊桥分配最小编号廊桥更新该廊桥的承载计数并将廊桥标记为占用无空闲则该航班停靠远机位。法一全部枚举出方案。45分#includebits/stdc.husingnamespacestd;intn,m1,m2;intjs(vectorpairint,intv,intk){if(k0)return0;priority_queueint,vectorint,greaterintq;intres0;for(inti0;iv.size();i){intlv[i].first;intrv[i].second;while(!q.empty()q.top()l)q.pop();if(q.size()k){q.push(r);res;}}returnres;}intmain(){cinnm1m2;vectorpairint,intd(m1);vectorpairint,intg(m2);for(inti0;im1;i)cind[i].firstd[i].second;for(inti0;im2;i)cing[i].firstg[i].second;sort(d.begin(),d.end());sort(g.begin(),g.end());intans0;for(inti0;in;i){intcnt_djs(d,i);intcnt_gjs(g,n-i);ansmax(ans,cnt_dcnt_g);}coutans;return0;}法二我们知道分配更少廊桥数时可停靠的飞机在分配到更多廊桥数时一定也能停靠。可以参考下面这个表所以把模拟流程的函数改一下最后返回每个廊桥停的飞机数。而飞机总数是前缀和所有此前飞机再加上新增飞机数即目前最后一个廊桥所装飞机。#includebits/stdc.husingnamespacestd;intn,m1,m2;vectorintjs(vectorpairint,intv,intk){vectorintres(k1,0);priority_queueint,vectorint,greaterintq_id;//空闲廊桥编号priority_queuepairint,int,vectorpairint,int,greaterpairint,intb_id;//廊桥的编号和离开时间for(inti1;ik;i){q_id.push(i);}for(inti0;iv.size();i){intlv[i].first;intrv[i].second;while(!b_id.empty()b_id.top().firstl){intidb_id.top().second;b_id.pop();q_id.push(id);}if(q_id.empty())continue;intidq_id.top();q_id.pop();res[id];b_id.push({r,id});}returnres;}intmain(){cinnm1m2;vectorpairint,intd(m1);vectorpairint,intg(m2);for(inti0;im1;i)cind[i].firstd[i].second;for(inti0;im2;i)cing[i].firstg[i].second;sort(d.begin(),d.end());sort(g.begin(),g.end());intans0;vectorintcdjs(d,n);vectorintcgjs(g,n);vectorintpd(n1,0),pg(n1,0);for(inti0;in;i){pd[i]pd[i-1]cd[i];pg[i]pg[i-1]cg[i];}for(inti0;in;i)ansmax(ans,pd[i]pg[n-i]);coutans;return0;}假设n1所以一共有9×5(拨一个拨圈)9×4(拨两个拨圈)81种。直接输出81可以得高达30分哦正解这道题枚举所有情况来讨论可以做对。如果按每一位不同情况设置就会有五层循环显然不可取。所以得按数字加一再数位分离得到。但注意i从100000开始到199999结束。如果是00000数位分离结果会是0。然后就是判断这个数是否可取。可以用一个循环遍历所有状态在与之对比。若有2位以上或0位不同就不合法若只有一位则必定合法若有两位就得看是否相邻转动幅度是否一样。#includebits/stdc.husingnamespacestd;intn,a[6],b[10][5],ans0;boolcheck(inta[],intb[][5]){for(inti0;in;i){ints0;for(intj0;j5;j){if(b[i][j]!a[j])s;}if(s2||s0)return0;if(s1)continue;for(intj0;j5;j){if(b[i][j]!a[j]){if(b[i][j1]a[j1])return0;elseif((b[i][j]-a[j]10)%10(b[i][j1]-a[j1]10)%10){break;}elsereturn0;}}}returntrue;}intmain(){cinn;for(inti0;in;i){for(intj0;j4;j){cinb[i][j];}}for(inti100000;i199999;i){intxi;for(intj4;j0;j--){a[j]x%10;x/10;}if(check(a,b)){ans;}}coutans;return0;}一道简单的模拟题。两个变量一个存需要多少天用一个while让苹果数每天自减1/3向上取整另一个存第n个需要多少天用一个while让n每天自减1/3向上取整当n%31时break。#includebits/stdc.husingnamespacestd;intmain(){intn,x;cinn;xn;intcnt0,day0;while(x){xx-ceil(x/3.0);cnt;}while(true){day;if(n%31)break;nn-ceil(n/3.0);}coutcnt day;return0;}
阅读完成 · 觉得有帮助？
