ZOJ3981 CCPC秦皇岛站A题

题目链接

题意：
有一个圆形的桌子，桌子周围有m个位置，有m个队伍。然后第a个队伍会在第p时刻做出一道题目来，有一个机器人来给做出题目的队伍发气球。如果你在a时刻A了一道题目，而你在b时刻得到的气球，就会产生b-a的不开心值。
机器人出发位置是不确定的，求最小不开心值。

题解：
先求出机器人从位置1出发，所有题目产生的不开心值。
这里要注意事件发生的顺序，即是机器人先动，然后队伍A题，然后发气球。（刚开始就没看到……）
求出所有不开心值之后，排个序。
第i个题目以1为出发点的不开心值应为 ：（i的位置 - 1（出发点）-做出这个题的时间 + m）%m
然后枚举每一个题目，看这个题目的不开心值为0的时候总的不开心值，不断更新。
设 un[i] 为题目i的不开心值：
对于题目i来说，它以前进un[i]个单位的位置为出发点时，题目i产生的不开心值为0，那么i之后的题目j的不开心值就是un[j]-un[i];而i之前的题目k的不开心值则是(un[k] - un[i] + m) % m。
那总的公式就是sum + m * (i - 1) - un[i]*q。

一直对于当初只是看了一眼题意而没有开这个题而有一丝遗憾，现在倒是释然了，这个题如果当初做也很大几率做不出来。还是太菜了QAQ。
（倒是开场前还看着A题的黄色气球志愿者打的贼多还猜这个题是签到题23333333）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn = 100005;
const int inf = 0x3f3f3f3f;
ll n,m,p;
ll seat[maxn];
ll un[maxn];
int main()
{
int tes;
ll temp,temp1;
scanf("%d",&tes);
while(tes--)
{
memset(seat,0,sizeof seat);
memset(un,0,sizeof un);
scanf("%lld %lld %lld",&n,&m,&p);
for (int i = 1; i <= n; i++)
{
scanf("%lld",&seat[i]);
}
for (int i = 1; i <= p; i++)
{
cin>>temp>>temp1;
un[i] = (seat[temp] - 1 - temp1 + m) % m;
}
sort(un + 1,un + p + 1);
ll sum = 0;
for (int i = 1; i <= p; i++)
sum += un[i];
ll ans = 1e18;
for (int i = 1; i <= p; i++)
{
if(un[i])
{
ans = min(ans, sum + m * (i - 1) - un[i]*p);
}
}
cout<<ans<<endl;
}
}

最后

以上就是哭泣马里奥为你收集整理的ZOJ3981 CCPC秦皇岛站A题的全部内容，希望文章能够帮你解决ZOJ3981 CCPC秦皇岛站A题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。