SCUT - 483 - 数轴上的点

https://scut.online/p/483

改了题目之后发现，其实n个点放在[1,2N]，要求间距至少是2，那么有且只有一个点和前面点的间距是3（设-1存在一个点），其他点的间距都必须是2。排序后枚举这个点，这个点之前的点向左移动到尽头，这个点及其之后的点向右移动到尽头。显然这样考虑了所有的情况。考虑如何计算花费，预处理每个排序后的点去往他要去的位置的左尽头和右尽头绝对值前缀和，那么枚举断点的时候可以计算出两端的花费，假如是当前最低的则加入答案之中。

当时读错题了，以为不同移动的路径属于不同方法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000000 + 5;
const ll INF = 1e18;

int n, a[MAXN], l[MAXN], r[MAXN];
ll prefixl[MAXN], prefixr[MAXN];

ll minsum;
int mini[MAXN], mitop;
//mini把i及其右侧的归到右边会产生最小值

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    while(~scanf("%d", &n)) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + 1 + n);
        for(int i = 1; i <= n; ++i) {
            l[i] = abs(a[i] - (2 * i - 1));
            r[i] = abs(a[i] - (2 * i));
            prefixl[i] = prefixl[i - 1] + l[i];
            prefixr[i] = prefixr[i - 1] + r[i];
        }
        mitop = 0;
        minsum = INF;
        for(int i = 1; i <= n + 1; ++i) {
            if(prefixl[i - 1] + prefixr[n] - prefixr[i - 1] <= minsum) {
                if(prefixl[i - 1] + prefixr[n] - prefixr[i - 1] == minsum) {
                    mini[++mitop] = i;
                } else {
                    minsum = prefixl[i - 1] + prefixr[n] - prefixr[i - 1];
                    mini[mitop = 1] = i;
                }
            }
        }
        printf("%lld %d\n", minsum,mitop);
    }
    return 0;
}

SCUT - 483 - 数轴上的点

原文：https://www.cnblogs.com/Yinku/p/11337950.html