链接:zoj3981

题解

假设站在第一个点每个AC的不满意度则是d[i]=(s[a]+m-1-b)%m，可能出现负数，没关系，之后会处理这种情况。
然后sort一下站在第一个点的不满意度,显然如果站在第i个AC点，d[i]会变成0，之后每个点都会变成d[j]-d[i],之前的每个点会变成d[j]-d[i]+m。这也正好处理了出现负数的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define repd(i,x,y) for(int i=x;i>=y;--i)
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
const int N=1e5+7;
const ll lnf=0x3f3f3f3f3f3f;
ll ans,d[N],res,a,b,s[N],n,m,p,T;
int main(){
	scanf("%d",&T);
	while(T--&&~scanf("%d%d%d",&n,&m,&p)){
		res=0;ans=lnf;
		rep(i,1,n)scanf("%d",&s[i]);
		rep(i,1,p){
			scanf("%lld%lld",&a,&b);
			d[i]=(ll)((ll)s[a]+m-1-b)%m;
			res+=d[i];
		}
		sort(d+1,d+p+1);
		rep(i,1,p)ans=min(ans,res+m*(i-1)-d[i]*p);
		printf("%lld\n",ans);
	}
	return 0;
}