题目链接

大意：

有一个长度为m的圆形桌子，有n支队伍。然后有p次ac。每次ac给出ac的队伍编号和ac的时间。

有一个专门发放气球的机器人，他按照顺时针的方向绕着圆形桌子，一秒移动一个座位。当他移动

到第i个位置的时候，他会给下一个位置发放气球。发放气球的数量是该座位上次放气球的时间到

这次发放气球的时间中ac的数量。当一个队伍ac后，如果不能立即得到气球，这支队伍就会产生

怒气值。怒气值会累加。直到机器人给这次ac发放气球为止。（也就是说如果一支队伍在第t秒ac

了一道题，如果这次ac的气球是在第t1秒发放的，那么这次ac的怒气值就是t1 - t）。

给你每支队伍坐的位置编号和每次ac的队伍编号和时间，问如何安排机器人的位置使得总的怒气值最小。

 

大致思路：

我们先假定当机器人位置x,每次ac的队伍编号为a,时间为t, 那么每次ac的怒气值为(site[a] - ((t + x) % m) + m) % m;

我们可以得到样例2在机器人位置为1的时候每次ac的值是

2 0 1 0 2；

如果机器人位置如果移动到第x位的话，那么怒气值比x小的话会增加m - x, 比x大的怒气值会 - 1；

那么我们如果将机器人位置为1时每次ac的值排个序，那么我们当我们移动机器人的时候我们就可以在O(1)的时间求出

总的怒气值了。

我们如果让机器人遍历一遍桌子，复杂度为O(m)会超时。这m个位置有一些很容易就能看出是不能选的。

所以我们在存在某次ac的怒气值为0的时候才能使得总的怒气值最小(这一点不会证明)；

这样我们就把复杂度降到O(p)了；

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define mmset(a,b) memset(a,b,sizeof(a))
#define ll long long
using namespace std;

const int N = 1e5 + 5;

ll n,m,p;
ll site[N];
ll data[N];

/*
4
2 3 3
1 2
1 1
2 1
1 4
2 3 5
1 2
1 1
2 1
1 2
1 3
1 4
3 7 5
3 5 7
1 5
2 1
3 3
1 5
2 5
2 100 2
1 51
1 500
2 1000
*/
int main()
{
	ll T;
	scanf("%lld",&T);
	while(T--)
	{
		 scanf("%lld %lld %lld",&n, &m, &p) ;
		 for(int i = 1; i <= n; i++)
		 {
		 	scanf("%lld",&site[i]);
		 }
		 long long sum = 0;
		 for(int i = 1; i <= p; i++)
		 {
		 	ll a,b;
			scanf("%lld %lld",&a,&b) ;
			data[i] = (site[a] - ((b + 2) % m) + m ) % m;   //推论出当机器人位置为1的时候 每次ac的怒气值。 
			sum += data[i];   
		 }
		
		sort(data + 1, data + 1 + p) ;  //排序每次ac的怒气值，以便于在O(1)的时间推迟总的怒气值。 
		 
		 long long  res = 1e18;
		 for(int i = 1; i <= p; i++)    //遍历p次的ac,求出使得本次ac的怒气值为0的时候总的怒气值。 
		 {
		 	res = min(res, sum + (i - 1) * (m - data[i]) - data[i] * (p - i + 1));
		 }
		 printf("%lld\n",res);
	}
	return 0;
}