CCF-29次-第二题
创始人
2025-05-31 15:00:01

前言

比赛的时候100AC了，但现在是仅凭印象敲出来的代码，不确定是否会存在一些问题，等题目出来了，AC后，我再回来填坑，现在仅供参考。

分析

先将所有的天数尽量抹平。

即想象用柱状图来表示天数，从上往下把高的给抹平：
每抹去一定的高度，资源就需要相应减少；
等一样高了，资源的就是减去所有的num。

代码思路

  1. 排序，按天数递减，那么此时柱状图一定是高—>低（也可能有平）

  2. 我们从左往后遍历，如果遇到了坡，那我们就需要把从0~当前位置的土堆都铲平。
    （1）判断能否抹平？
    优化1：用mon记录前面的资源量，避免双重循环，增加时间复杂度。
    计算a[i-1].d-a[i].d和m/mon的大小，如果可以抹平，就直接减去资源，记录目前最长天数是a[i].d
    优化2：如果不可以完全抹平，那需要计算，至少可以铲掉多少？然后结束循环：m=0; ans-=a[i].d-m/mon;

  3. 所有山坡都铲成一个高度后，计算如果m还有剩余，是否可以把整个山坡都铲掉一些高度：count=m/sum;

  4. 取k和ans-count的最大值

代码

#include
using namespace std;
struct node{int d;int num;
}; 
bool cmp(const node&l,const node&r){if(l.d!=r.d)return l.d>r.d;return l.num>r.num;
}
vector a;//用数组也可以 
int main(){int n,m,k;int sum=0;//计算全部-1天的消耗 cin>>n>>m>>k;//个数  资源数  至少天数for(int i=0;i//用数组也可以 node temp;cin>>temp.d>>temp.num;a.push_back(temp);sum+=temp.num; } sort(a.begin(),a.end(),cmp);int mon=0;//存储a[i]之前的消耗量int ans=a[0].d;//答案 初始化等于最大的天数 for(int i=1;imon+=a[i-1].num;//存储a[i]之前的消耗量if(a[i].d//如果天数不相等，处理，让他们相等 int temp=m/mon;//现有资源最多能把前面1 ~ i-1减多少天？ if(temp>=(a[i-1].d-a[i].d)){//满足条件，能减 抹平天数 m-=temp*mon;//资源- ans=a[i].d;//更新目前最长的天数 } else {//不满足条件，说明没法减去那么多 直接break; m=0;ans=a[i-1].d-temp; break;} } } //如果此时m还有很多剩余，计算全部抹平的机会 int count=m/sum;	 cout<

上一篇：玩家必看“皇后斗牛可不可以开挂”原来确实有挂

下一篇：最新消息“毛豆大厅有挂吗”开挂方法

相关内容

热门资讯

“25年会员费”冲上热搜！ 折... 一则罕见的“25年会员费难退”事件，让爱奇艺冲上风口浪尖，穿透阵阵质疑声浪，爱奇艺的隐忧若隐若现~0...
协鑫能科及多名高管被深交所通报... 因控股股东非经营性资金占用、未按规定审议和披露关联交易等违规行为，协鑫能科（002015.SZ）及其...
同行者说：驶向中东中亚蓝海，我... 作者｜廉美真中东中亚，这片方兴未艾的新兴市场，在 2025 年依旧保持着蓬勃向上的发展势头。不同于前...
金科股份，还没有摘下“紧箍咒”... 斑马消费 杨柘对于*ST金科来说，卸下重整的包袱，轻装上阵，只是完成万里长征第一步，接下来将是推动企...
向正餐要增量，卤味三雄集体变“... 斑马消费 陈晓京当热卤转身一变成主角，消费者也悄然完成了从冷卤到热食的转变。譬如，绝味食品售价4.9...