题目链接：http://codeforces.com/contest/1130/problem/D2
题目大意
考虑特定的一个站台，其要完成
k个糖果的配送并要送往x1,x2,..xk，
我们通过手动模拟不难发现要想最优的完成
这个站台的配送，最后到达的点是离当前点最近的x值。
并且有几个糖果就转几圈，如果在x集合中出现了比当前站台序号大的，
那么圈数减一。
题目分析
对于离站台的糖果最近距离可以在输入的时候就预处理出来，
并且不随着开始点的改变而改变，那么随着开始节点的移动，
我们再扫描一遍站台数组，把当前站台节点和对这个站台糖果而言的
最后到达的相对序号求出来即可，可以通过这两个数值的关系来凑出关于当前站台的答案，
由于到达不同的站台可以无限卸载，所以每个最大值是独立的，
最终的答案就是取最大值的最大值。
时间复杂度：O(n*n).
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
int mod=20100501;
const int maxn=5e4+10;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
给定一个环形结构，火车只能沿固定方向行驶。
每个站台上有若干个糖果，每个糖果都指定要
送往x站台，每次到站火车最多只能装上一颗糖果，
但可以卸下无限糖果并且不计时间，问把这些糖果配送完
最少时间花费是多少。题目分析：
考虑特定的一个站台，其要完成
k个糖果的配送并要送往x1,x2,..xk，
我们通过手动模拟不难发现要想最优的完成
这个站台的配送，最后到达的点是离当前点最近的x值。
并且有几个糖果就转几圈，如果在x集合中出现了比当前站台序号大的，
那么圈数减一。对于离站台的糖果最近距离可以在输入的时候就预处理出来，
并且不随着开始点的改变而改变，那么随着开始节点的移动，
我们再扫描一遍站台数组，把当前站台节点和对这个站台糖果而言的
最后到达的相对序号求出来即可，可以通过这两个数值的关系来凑出关于当前站台的答案，
由于到达不同的站台可以无限卸载，所以每个最大值是独立的，
最终的答案就是取最大值的最大值。
时间复杂度：O(n*n).
*/
int n,m,INF;
int x[maxn],y[maxn];
int cnt[maxn],flag[maxn],mv[maxn];
int main(){cin>>n>>m;mst(mv,0xf),INF=mv[0];for(int i=0;i<m;i++){cin>>x[i]>>y[i];x[i]--,y[i]--;cnt[x[i]]++;int len=(y[i]-x[i]+n)%n;if(len<mv[x[i]]) mv[x[i]]=len;}rep(i,0,n){int ans=0;rep(j,0,n){if(mv[j]==INF) continue;int tp1=(j-i+n)%n,tp2=(tp1+mv[j])%n;if(tp1<tp2) ans=max(ans,(cnt[j]-1)*n+tp2);else ans=max(ans,cnt[j]*n+tp2);}cout<<ans<<" ";}puts("");return 0;
}
附上暴力过小数据的版本
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
int mod=20100501;
const int maxn=3e2;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
int n,m;
int x[maxn],y[maxn],mark[maxn];
vector<int> p[maxn];
int main(){cin>>n>>m;for(int i=0;i<m;i++){cin>>x[i]>>y[i];x[i]--,y[i]--;}int val=0;rep(i,0,n){val++;rep(j,0,m){int tx=(x[j]-i+n)%n,ty=(y[j]-i+n)%n;p[tx].push_back( -((ty-tx+n)%n) );}rep(i,0,n) sort(p[i].begin(),p[i].end());int idx=0,ans=0,tot=m;while(tot){while(p[idx].size()==0) idx=(idx+1)%n,mark[idx]=val-1,ans++;int tx=-p[idx][0];p[idx].erase(p[idx].begin());mark[(tx+idx)%n]=val;tot--,ans++,idx=(idx+1)%n;mark[idx]=val-1;}int tmp=0;while(mark[idx]==val-1&&tmp<n)idx=(idx-1+n)%n,tmp++;ans+=n-tmp;cout<<ans<<" ";}puts("");return 0;
}