题目链接: Mister B and PR Shifts
大致题意
给定一个长度为n的序列, 里面的元素为n的一种排列.
我们用 ∑i=1 i=n |Pi - i| 来表示整个数组的的花费.
我们可以让整个数组进行rotate操作, 所有元素整体右移k, 多出来的元素则补到最开头(相当于数组是个循环链表)
问最小花费是多少, 此时k为多少. (可以输出任意的答案)
解题思路
假设这个序列在右移的过程中,不会形成环, 我们较容易想到, 对于初始情况而言, 如果将序列整体右移1,则p[i] > i的位置使得花费减小, 反之会使得花费变大.
那么考虑到形成环, 假设我们还是只把序列整体右移1, 唯一被影响的位置其实只是第n个元素. 我们只需要对他特殊处理即可.
由于k < n, 因此我们可以通过从0~n-1枚举k的方式, 使得序列每次都是右移1, 然后处理出当前情况下的花费. 每次对于1~n-1位置的元素, 假设有sub个元素会使得花费减小, 则有add = n - 1 - sub个元素会使得花费变大, 因此影响为add - sub. 然后再特殊考虑第n个元素即可.
接下来的问题就是, 我们如何每次O(1)的去维护add与sub, 我们不难发现, 只有当a[i] = i时, 此时这个位置的贡献会发生逆转, 因此我们只需要统计当右移k的时候, 有多少个元素位于a[i] == i这样的位置即可. 我们可以采用cou[]数组, 表示第k次右移时有多少个元素符合要求.
那么对于第k次右移, 此时会有cou[k]个元素符合要求,则add会增加cou[k]. 但是考虑到我们的add和sub都是不计算n位置的元素, 而右移k次后, n位置的元素原本一定是属于add中的, 因此add还需要减少1.
AC代码
#include <bits/stdc++.h>#define rep(i, n) for (int i = 1; i <= (n); ++i)using namespace std;typedef long long ll;const int N = 1E6 + 10;int a[N], cou[N];int main(){int n; cin >> n;ll sum = 0; int add = 0, sub = 0;rep(i, n) {scanf("%d", &a[i]);sum += abs(a[i] - i);cou[(a[i] - i + n) % n]++;if (i == n) break; //不统计第n个元素if (a[i] > i) sub++;else add++;}ll res = sum; int resk = 0;rep(i, n - 1) {sum += add - sub;int last = a[n - i + 1];sum += abs(last - 1) - abs(last - n);add = add + cou[i] - 1; //记得要把第n个元素从add中抛出去sub = n - 1 - add;if (sum < res) res = sum, resk = i;}cout << res << ' ' << resk << endl;return 0;}
