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<

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

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

相关内容

热门资讯

魏建军回应“九年八换CEO”：... 出品丨虎嗅汽车组作者丨魏微头图丨长城汽车“有人说我们（魏牌）换了不少的CEO了，的的确确是这么回事，...
东方雨虹子公司疑遭电诈被骗逾千... 12月23日晚，东方雨虹公告，公司近日获悉，公司下属美国全资子公司OYH建材公司疑遭电信诈骗，涉案金...
造孽，挖了个大大坑 图： Antоn Gudim 年底了。 我一个女朋友给我晒她的账户，她买了几个ETF，基本都持有3-...
21天翻倍！溢价近60%，白银... 白银的火热，正以一种近乎疯狂的方式在二级市场上演。12月23日，国投白银LOF再度斩获涨停，实现两连...
快手不是我朋友 马上就要元旦了，那一天不但有元旦，还有新修订的《中华人民共和国治安管理处罚法》。那里面不但有前一段热...