CF819B Mister B and PR Shifts 解题报告

题目

传送门：https://www.luogu.com.cn/problem/CF819B

题意翻译

• 定义一个全排列 p~i~ 的偏移值为(sum_{i=1}^n)| p~i~ - i |
• 给你一个全排列，你可以从后面拿k∈[0,n−1]个数放在前面，使得该全排列的偏移值最小，输出这个偏移值和k，如果有多个k任意输出一个
• n ≤ 10^6^

开整

（不看翻译是真的看不懂……）

上来一看以为要用差分，莽一波欢乐报零。于是换个思路想一想。

就暴力而言，我们是从后往前，一个一个拿到最前面，然后再扫一遍判断ans的变化。

于是乎，转念一想，我们当前位的数的本身的大小是不变的，而我们每操作一次它的编号 i 就会增大1 。

那么，对于原先偏移值（注意这个“原”是对于当前次操作而言，而并非是最开始的那个，下面的也是一样，我们的偏移值是在随着操作不断改变的）为正数的，显然对ans的贡献量会减少1，即ans一共会减少原偏移值为正的数的个数。

对于原偏移值为非正的，显然对ans的贡献会加1，所以ans的增加量是原偏移值为非正数的数的个数。

所以，我们要维护的就是原偏移值为正的和非正的数的个数。

然后我们就可以考虑了，经过一次操作，原偏移值为+1的数偏移值都会变为0，也就是说，原偏移值为正数的数的个数会少掉原偏移值为+1的数的个数。

而原偏移值为非正数的数的个数会加上原偏移值为+1的数的个数，这也是显然的。所以原偏移值为非正的数的个数不会变少，只会越来越多。

另外，每次操作我们把第 n-i+1 位的数放到最前面，这个数所带来的偏移值的改变直接计算即可。

这样我们整个时间效率应该是稳定的O(2n)，然后这题最好别用cin，cout...虽然能过，但是我加优化都跑了15s...

然后，就这样。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
char buf[1 << 20], *p1 = buf, *p2 = buf;
char getc() {
	if(p1 == p2) {
		p1 = buf;
		p2 = buf + fread(buf, 1, 1 << 20, stdin);
		if(p1 == p2) return EOF;
	}
	return *p1++;
}
inline int read() {
	int s = 0, w = 1;
	char c = getc();
	while(c < '0' || c > '9') {if(c == '-')w = -1; c = getc();}
	while(c >= '0' && c <= '9') s = s * 10 + c - '0', c = getc();
	return s * w;
}
const int maxn = 3e6 + 10;
int a[maxn];
ll ans = 0, k = 0;
ll zheng_cnt, fu_cnt;
ll one[maxn];//第i次操作时原偏移值为1的数的个数就是one[i]，大家想一想就知道了。
int main(){
    int n = read();
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        int x = a[i] - i;
        if(x <= 0) {
            fu_cnt++;
            ans += abs(x);
        }
        else {
            zheng_cnt++;
            ans += x;
            one[x]++;
        }
    }
    ll tmp, tmpp = ans;//为了避免错误地修改ans，咱们用两个中间变量跑循环
    if(ans == 0) {//一些剪枝优化，但感觉没什么卵用
        printf("0 0
");
        return 0;
    }
    for(int i = 1; i < n; i++){//没什么好说的了
        tmp = tmpp;
        tmp -= zheng_cnt;
        tmp += fu_cnt;
        zheng_cnt -= one[i];
        fu_cnt += one[i];
        
        //对这个挪动的数进行操作
        ll x = a[n - i + 1];
        tmp -= n + 1 - x;
        fu_cnt--;
        if(x > 1) {
            one[x - 1 + i]++;
            tmp += x - 1;
            zheng_cnt++;
        }
        else fu_cnt++;
        //操作结束
        
        if(tmp < ans) {
            ans = tmp;
            k = i;
        }
        if(ans == 0) {//还是剪枝，依然是没什么卵用
            printf("0 %lld
", k);
            return 0;
        }
        tmpp = tmp;//记得循环一下变量，不然整个过程就不是连续的了
    }
    printf("%lld %lld
", ans, k);
    return 0;
}