CCPC 秦皇岛 A ：Balloon Robot

题目传送门

Description

机器人绕着桌子转，桌子上的人在ACM，一直n个人的位置 ， 共m个座位 ，所有人一共Al了P 题 。 给出A的人 和 时间 ， 问最少的等待时间是？

Solution

在codeforces上好像有过相似的题 ， 预处理答案 ，枚举关键点 ，O(plgn);
先假定机器人初始位置为0 ， 那么答案就是 Sum(pos - time%m + m )%m , 对于每一个x ， 答案变成 (pos - time%m + m)%m - x ,但这个值可能是负的 ， 所以每次枚举x，找出是负值的个数q ， 预处理的答案 + q * m , 就可以了。
具体实现就是排序后用lower_bound

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int ,int >
#define x first
#define y second
#define MEM(a) memset(a,0,sizeof(a))
#define Rep(i,n) for(int i = 0;i < n;i++)
#define For(i,n) for(int i=1;i<=n;i++)
#define LL long long 
#define MAX 100005
#define pb push_back
LL n , m , p ;
LL pos[MAX];
vector<LL>key; // key postion
vector<LL>que;
LL ans , sum ;
int main(int argc, char const *argv[])
{
// freopen("data.in","r",stdin);
int TT;scanf("%d",&TT);
while(TT--) {
MEM(pos);key.clear();que.clear();sum = 0;ans;
scanf("%lld%lld%lld",&n,&m,&p);
For(i,n) scanf("%lld",pos+i);
Rep(i,p) {
LL po, ti ; scanf("%lld%lld",&po,&ti);po = pos[po];
key.pb((po - ti%m + m )%m);
sum += (po - ti%m + m )%m;
que.pb((po - ti%m + m)%m);
}
sort(key.begin(),key.end());
key.erase(unique(key.begin(), key.end()), key.end());
sort(que.begin(),que.end());
ans = sum;
Rep(i,key.size()) {
LL q = lower_bound(que.begin(),que.end(),key[i]) - que.begin();
ans = min(ans , sum + q * m - key[i] * p);// ....
}
printf("%lldn",ans);
}
return 0;
}

最后

以上就是大胆身影为你收集整理的2017 CCPC 秦皇岛 A：Balloon RobotCCPC 秦皇岛 A ：Balloon Robot的全部内容，希望文章能够帮你解决2017 CCPC 秦皇岛 A：Balloon RobotCCPC 秦皇岛 A ：Balloon Robot所遇到的程序开发问题。

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