大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
话说，我终于AC了这个题
这是一个贪心，说实话开始做的时候……完全没看出来QAQ。。
可能有人说这是个dp,但这真不是(dalao请无视)
这真的只是个贪心。。。。
首先对于每个点当然是能走就走，
不能走就等待，这是无法控制的。
所以只考虑氮气加速器加在哪里可以使时间总和尽量少。
所以
如果选择加速，可能会使后面等待的时间更长，或者更短，对后面都会有影响。
但是沿着一条边加速会影响后面的所有边么？
这可不一定
来来来，我们分类讨论一下：
1.到下一个点还需要等待：以后的时间就不再影响了
2.到下一个点不需要等待：对以后的时间还会加速直到……出现情况1（或者到最后一个点）！！
即每次用加速器都会对后面的人有影响，
用 $ sum_i $ 记录到i的人数，前缀和处理， $ g_i $ 代表每个点所能影响到的最远点，
那么 $ sum_{i + g_i} – sum_i $ 即是能影响到的人数
这样就很容易想到选择影响尽量大的点减掉（在这里贪心）。
CODE:
/*last[i] : 最后一个人到达i站点的时间。 sum[i] : 到i站点的总人数。 enter[i] : 公交车到i站点的最少时间。 g[i] : 每个站点所能影响到的最远站点，即要求的影响。*/ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define N 30001 using namespace std; int n,m,k; int dis[N],last[N],g[N],enter[N]; int ans,sum[N],maxx = -1; struct node { int time,start,end; }a[N]; inline void bus(int x) { while(x) { --x; g[n] = g[n - 1] = n; int tar; maxx = -1; for(int i = n - 2 ; i >= 1 ; -- i) { if(enter[i + 1] <= last[i + 1])//下一个点如果等待 g[i] = i + 1;//最多影响到下一个 else //不等待 g[i] = g[i + 1];//继续减少后面的时间 } for(int i = 1 ; i < n ; ++ i){//for边数 int tmp = sum[g[i]] - sum[i];//最多影响的人数 if(tmp > maxx && dis[i] > 0){ maxx = tmp; tar = i;//标记最优情况减的点 } } ans -= maxx;//更新ans dis[tar] --;//减掉dis for(int i = 2 ; i <= n ; ++ i) enter[i] = max(enter[i - 1],last[i - 1]) + dis[i - 1];//重新更新enter } return; } int main(){ scanf("%d%d%d",&n,&m,&k); for(int i = 1 ; i < n ; ++ i) scanf("%d",&dis[i]); for(int i = 1 ; i <= m ; ++ i) scanf("%d%d%d",&a[i].time,&a[i].start,&a[i].end); for(int i = 1 ; i <= m ; ++ i) { last[a[i].start] = max(last[a[i].start],a[i].time);//最后一个人到a[i].start站点的时间 和到这个点的时间取max sum[a[i].end] ++; } enter[1] = last[1]; for(int i = 1 ; i <= n ; ++ i) sum[i] += sum[i - 1];//到i站点的总人数 前缀和处理 for(int i = 2 ; i <= n ; ++ i) enter[i] = max(enter[i - 1],last[i - 1]) + dis[i - 1];//公车到i站点的最少时间 和最后到的时间取max for(int i = 1 ; i <= m ; ++ i) ans += enter[a[i].end] - a[i].time;//处理出不加加速器的answer,后面就可以直接减啦~ bus(k); printf("%d \n",ans); return 0; }真的是考验智商QAQ…
转载于:https://www.cnblogs.com/Repulser/p/10665627.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/189785.html原文链接：https://javaforall.net
