admin 管理员组文章数量: 887032
CF 1129 A,B
A 题目就是一个环，每个节点上可能有 n 个糖果，需要把这个糖果从这个点 送到 k，没跑一个节点会耗1s
问以每个不同节点为起点的最短送完全部糖果时间，每次只能运送一个糖果。
因为每个只能运1个， 所以 有 k 个糖果要走k次，那么以 a 为起点，我们想，走的比较远的就转圈时候处理掉，把最近那个留到最后一圈，最后再跑最短的，对于每个点 耗得时间就是 n*(k-1) + min_dis（ i ） 当然我们需要以 a 为起点时候，要以 b 为终点，遍历一遍，时间复杂度为 O(n^2)，之后我们只要找出到所有终点最短距离就好了，当然终点也要全部走完。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2e5+5;
int num[maxn],dis[maxn];
int main()
{int n,m;cin>>n>>m;memset(dis, 0, sizeof dis);for(int i=1;i<=m;i++){int a,b;cin>>a>>b;num[a]++;int temp = b>a ? b-a:b+n-a;if(dis[a] == 0) dis[a] = temp;else dis[a] = min(dis[a], temp);}for(int i=1;i<=n;i++){int ans = 0;for(int j=1;j<=n;j++){if(j >= i){ans = max(ans, n*(num[j]-1)+dis[j]+j-i);}else{ans = max(ans, n*(num[j]-1)+dis[j]+j+n-i);}}cout<<ans<<' ';}return 0;
}
B.巧妙地一题，我们既然要找出一个 答案比爱丽丝算法大 k 的数组
我们的算法很简单 sum(0-n-1)*n 而爱丽丝遇到负数就清零，这个数组我们自己决定，
那么根据万物之敌贪心思路，数组开为 2 的话 一个负数，一个正数，就可以搞了
设为 -x 和 x+d 那么我们的结果是 2*d 爱丽丝是 x+d 差就是 d-x = k , d = x + k
当然这个数字我们自由决定，但是问题来了， ai < 1e6 所以，我们如果 长度为 2 那么很显然，炸了（虽然我卡在这了，但是看到一个大佬思路。。。）
3也炸了。。。那么我们再贪心一波， 长度 开到 2000
那么就是 2000*d - x - d = k 1999*d = k + x， d 是正整数
x 就是 1999 - k%1999（自己试几个数字）， d = (k+x)/1999 ，理论上解决了。。
附上大佬博客。。。思路太强了。。。
?#comment-495122
版权声明：本文标题：CF 1129 A,B 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687129710h67235.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论