题解：P9185 [USACO23OPEN] Rotate and Shift B

题目传送门

题目大意

有 n 个人围成一个圈，编号为 0 到 n-1，有 k 个活跃的位置 0=a_{1}<a_{2}<a_{3}<\cdots<a_{k}<n 在每一分钟，活跃位置上的人会发生移动，a_{1} 移动到 a_{2}，a_{i} 移动到 a_{i+1} 位置，a_{k} 移动到 a_{1}，k 个移动同时发生。

接下来活跃位置会发生改变：a_{1} 变成 a_{1}+1，a_{2} 变成 a_{2}+1，以此类推（如果 a_{i}=n-1，则 a_{i} 变为 0）。请求出 T 分钟后每个人的位置。

思路

在样例解释中，观察一列中一个数字出现的次数和位置。

Initial,
T = 0:  order = [0 1 2 3 4 ], A = [0 2 3 ]
T = 1:  order = [3 1 0 2 4 ], A = [1 3 4 ]
T = 2:  order = [3 4 0 1 2 ], A = [2 4 0 ]
T = 3:  order = [2 4 3 1 0 ], A = [3 0 1 ]
T = 4:  order = [1 2 3 4 0 ], A = [4 1 2 ]
T = 5:  order = [1 0 2 4 3 ], A = [0 2 3 ]
T = 6:  order = [4 0 1 2 3 ], A = [1 3 4 ]
T = 7:  order = [4 3 1 0 2 ], A = [2 4 0 ]
T = 8:  order = [2 3 4 0 1 ], A = [3 0 1 ]
T = 9:  order = [0 2 4 3 1 ], A = [4 1 2 ]
T = 10: order = [0 1 2 3 4 ], A = [0 2 3 ]

我们发现其中 0,1,3,4 每过 2 秒就会后移 2 个位置，而 2 每一秒都会后移 1 个位置。

可以自己多测几组样例，发现一个规律：

如果我们把 a_{i} 和 a_{i+1} 的差表示为 x。那么 a_{i} 和 a_{i+1}-1 之间所有数都是第一次走后每 x 秒向后移动 x 个数。

那么只需要把 0 \sim n-1 中的每个数按这个规律算一次 T 秒后的位置，并存在一个新数组的对应位置。最后输出就行了。

所有疑问和细节均体现在代码，代码注释和解释中。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,t;
ll a[200005],ans[200005];
ll xs(ll x,ll y){//向上取整 
    return (x+y-1)/y;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k>>t;
    for(ll i=0;i<k;i++) cin>>a[i];
    a[k]=n;
    for(ll i=0;i<k;i++){
        ll x=a[i+1]-a[i];//x 表示每次停的时间和每次走的距离。 
        for(ll j=a[i];j<a[i+1];j++){
            int p=xs(t-(j-a[i]),x)*x;//表示偏移量。 
            ll b=(j+p)%n;//用本身的值加上偏移量，注意 %n 保持在 0~n-1 范围内。 
            ans[b]=j;//记录答案。 
        } 
    }
    for(int i=0;i<n;i++) cout<<ans[i]<<" ";
    return 0;
}

j-a[i] 表示 j 第一次等多久才走。

t-(j-a[i]) 表示 j 一共等的时间。

xs(t-(j-a[i]),x) 等的时间除以一次等 x 分钟，向上取整。表示等了几次，相当于走了几次。为什么要向上取整？请读者自己思考。

xs(t-(j-a_{i}),x)*x 走的次数乘每次走的距离，表示偏移量。