P11232 题解题目思路20分观察了数据后我们不难发现特殊数据A是最简单的。当所有车的加速度均为0时只用判断这辆车的初始速度是否大于限速以及这辆车进入主干道时是否位于最后一个测速点之后就能判断它是否超速。用一个计数器cnt来存储超速车辆输出时只用判断一下cnt0还是cnt0就可以了。大于零输出cnt与m-1小于零输出0与m。40分又观察了一下发现特殊性质B也挺好拿分的。利用题目给的公式计算出这辆车会在哪里超速判断一下这个位置是否在最后一个测速点之后就可以了。输出同上。注意计算位置时为了保证精度我们可以不用开方而是将目标平方这样可以避免开方时的精度损失60分最后只剩下特殊性质C与4个普通点了。我们先来解决一下特殊性质C。首先判断一下这辆车的初始速度是否小于限速。如果小于就可以直接跳过。如果大于就查找p数组中这辆车的进入主干道后遇到的第一个测速仪。如果这辆车的入口在最后一个测速仪之后就跳过。为了提高效率这一部分我们可以用二分来实现。找到之后我们就可以二分求超速区间了。求出超速区间后我们就可以将区间存进一个数组中将区间按右端点从小到大排序这是在通过贪心求出最多能关闭多少个测速器后通过类似于区间覆盖的方式求解。80分把所有特殊性质处理完之后我们的目光就可以转向1,2号测试点了。由于数据范围较小我们可以暴力枚举所有测速器关闭的可能性用二进制枚举相信大家都会这里就不在详细讲解了100分通过对特殊性质ABC的分析我们就可以产生意的大胆的想法判断每一辆车的加速度分情况进行处理。思路与前面基本一样这里就不再详细讲解了。详细注释看代码代码实现#includeiostream#includevector#includealgorithmusingnamespacestd;// n车辆数m测速点数量l道路总长v限速intn,m,l,v;// 车辆结构体d车辆起始位置v初速度a加速度structnode{intd,v,a;}car[100005];intp[100005];// p数组存各个测速点的位置输入后升序// 区间结构体l是测速点下标左端点r测速点下标右端点structqujian2{longlongl-1,r-1;};vectorqujian2aa;// 区间排序比较函数按区间右端点从小到大排序贪心必备boolcmp(qujian2 a,qujian2 b){returna.rb.r;}// check1所有车加速度 a0 匀速的情况voidcheck1(){intcnt0;for(inti1;in;i){// 车辆起点 最后一个测速点位置并且初速度限速全程超速if(car[i].dp[m]car[i].vv){cnt;}}if(cnt0){// 至少保留1个测速点最多拆掉 m-1coutcnt m-1endl;}else{// 没有车超速所有测速点都可以拆掉cout0 mendl;}}// check2所有车加速度 a0 持续加速的情况voidcheck2(){intcnt0;for(inti1;in;i){intsp[m]-car[i].d;// 车到最后一个测速点走过的距离// 末速度平方 v0² 2*a*slonglongmaxv1LL*(car[i].v*car[i].v2*car[i].a*s);// 到最后测速点仍然超速并且车起点不超过最后测速点if(maxv1LL*v*vcar[i].dp[m])cnt;}if(cnt0){coutcnt m-1endl;}else{cout0 mendl;}}// check3所有车加速度 a0 减速的情况voidcheck3(){vectorqujian2aa;intcnt0;for(inti1;in;i){// 初速度本身不超过限速不可能超速跳过if(car[i].vv){continue;}// lower_bound找第一个 车辆起点d的测速点下标intl_idxlower_bound(p1,pm1,car[i].d)-p;if(l_idxm1)continue;// 所有测速点都在车起点前面测不到// 在第一个有效测速点判断是否超速longlongvsq_l1LL*car[i].v*car[i].v2LL*car[i].a*(p[l_idx]-car[i].d);if(vsq_l1LL*v*v)continue;// 二分找到最大下标last测速点last处该车仍然超速intlol_idx,him,lastl_idx;while(lohi){intmid(lohi)/2;longlongvsq1LL*car[i].v*car[i].v2LL*car[i].a*(p[mid]-car[i].d);if(vsqv*v*1LL){lastmid;lomid1;// 继续向右找更远还超速的测速点}else{himid-1;}}// 记录这辆车超速对应的测速点下标区间 [l_idx, last]qujian2 q;q.ll_idx;q.rlast;aa.push_back(q);cnt;}// 区间贪心按右端点排序sort(aa.begin(),aa.end(),cmp);ints-1;// s记录上一个选中测速点的下标intk0;// k最少需要保留多少测速点覆盖全部区间for(inti0;iaa.size();i){// 当前区间左端点 上一个选中测速点需要新增测速点if(saa[i].l){saa[i].r;// 贪心选区间最右侧点k;}}// cnt超速车辆总数m-k最多可以拆除测速点数量coutcnt m-kendl;}// check4n20m20数据很小暴力枚举所有测速点保留方案voidcheck4(){intmask[25];// mask[i]第i辆车哪些测速点会拍到它超速二进制标记for(inti1;in;i){mask[i]0;for(intj1;jm;j){if(p[j]car[i].d)continue;// 测速点在车起点前面测不到longlongvsq1LL*car[i].v*car[i].v2LL*car[i].a*(p[j]-car[i].d);if(vsq0)continue;if(vsq1LL*v*v){mask[i]|(1(j-1));// j号测速点能抓到该车标记第j-1位}}}intcnt0;for(inti1;in;i){if(mask[i]!0){cnt;// 存在测速点可以抓到该车属于超速车}}intmink30;// mink最少保留测速点数量初始设为大于m的值// 枚举所有保留测速点的组合 mask_1二进制1代表保留测速点for(intmask_10;mask_1(1m);mask_1){boolok1;for(inti1;in;i){// 如果这辆车会超速并且当前保留测速点没有任何一个能抓到它则方案非法if(mask[i]!0(mask[i]mask_1)0){ok0;break;}}if(ok){intcnt10;for(intj0;jm;j){if(mask_1(1j))cnt1;// 统计当前方案保留几个测速点}minkmin(mink,cnt1);// 更新最小保留数量}}coutcnt m-minkendl;}//check5:处理大数据混合情况voidcheck5(){// 混合情况有a0 / a0 / a0多种车辆统一求超速区间再贪心vectorqujian2aa;for(inti1;in;i){if(car[i].a0){// 匀速if(car[i].vv){continue;}intl_idxlower_bound(p1,pm1,car[i].d)-p;if(l_idxm1)continue;// 从l_idx到最后一个测速点全部超速aa.push_back({l_idx,m});}elseif(car[i].a0){// a0加速一旦超速后面所有测速点都会超速intlo1,him,first-1;while(lohi){intmid(lohi)/2;if(p[mid]car[i].d){lomid1;continue;}longlongvsq1LL*car[i].v*car[i].v2LL*car[i].a*(p[mid]-car[i].d);if(vsq1LL*v*v){firstmid;himid-1;}else{lomid1;}}if(first-1)continue;// first是第一个超速测速点之后全部超速aa.push_back({first,m});}else{// a0减速只会一段连续测速点超速后面速度降下来不再超速if(car[i].vv){continue;}intl_idxlower_bound(p1,pm1,car[i].d)-p;if(l_idxm1)continue;longlongvsq_l1LL*car[i].v*car[i].v2LL*car[i].a*(p[l_idx]-car[i].d);if(vsq_l1LL*v*v)continue;intlol_idx,him,lastl_idx;while(lohi){intmid(lohi)/2;longlongvsq1LL*car[i].v*car[i].v2LL*car[i].a*(p[mid]-car[i].d);if(vsqv*v*1LL){lastmid;lomid1;}else{himid-1;}}qujian2 q;q.ll_idx;q.rlast;aa.push_back(q);}}intcntaa.size();sort(aa.begin(),aa.end(),cmp);ints-1;intk0;for(inti0;iaa.size();i){if(saa[i].l){saa[i].r;k;}}coutcnt m-kendl;}intmain(){intt;cint;while(t--){boolflag0true,flagdtrue,flagxtrue;cinnmlv;for(inti1;in;i){cincar[i].dcar[i].vcar[i].a;if(car[i].a!0)flag0false;// flag0true代表所有车a0匀速if(car[i].a0)flagdfalse;// flagdtrue代表所有车a0加速if(car[i].a0)flagxfalse;// flagxtrue代表所有车a0减速}for(inti1;im;i){cinp[i];}// 1,2号测试点if(n20m20){check4();continue;}// 全部匀速if(flag0){check1();continue;}// 全部加速度0持续加速elseif(flagd){check2();continue;}// 全部加速度0减速elseif(flagx){check3();continue;}else{check5();continue;}}return0;}其实代码不用辣么长只保留check5就可以了