ARC138A Larger Score 题解

前言

题目传送门，到博客食用。
@Split_shadow 特荐我此题，现记录题目（已知），贪心方法（求证）与思路（证明），附上暴力思路（代码解析）。
只能说是一道用数据结构或神奇二分的神仙 贪心题。

思路证明

已知

现存在一个长度为 $n$ 的数列 $a_{1},a_{2},a_{3},a_{4}\dots a_{n}$，给定数 $k$，求最少的交换次数 $times$ 使得交换后的数列 $b$ 中 $(\sum_{i=1}^{k}b_{i})>(\sum_{i=1}^{k}a_{i})$。
（规定交换为 $\operatorname{swap}(a_{i},a_{i+1})$，且 $(1\le i<n)$）。

求证

为使 $times$ 尽量小，则所有交换操作和并起来应该是一次不比较大小的冒泡操作（即在 $a_{1}$ 到 $a_{k}$ 中仍有 $k-1$ 个不考虑位置的数不变）。

证明

假设在 $times$ 最小时，前 $k$ 个数中变换后不变的数（不考虑位置）小于 $k-1$ 个，即变化的数大于 $2$ 个。
先就 $2$ 个的情况讨论。
设在前 $k$ 个数中 $a_{x},a_{y}$ 在冒泡操作后被替换为 $a_{m},a_{n}(1\le x,y\le k<m,n)$。
则有：$a_{x}+a_{y}<a_{m}+a_{n}$。
不妨令 $a_{x}<a_{m}$（这个是一定存在的），且在 $a_{x},a_{y}$ 与 $a_{m},a_{n}$ 两组中，非同组元素互换时，$a_{x}$ 与 $a_{m}$ 互换冒泡所费次数最少。
则存在一种方案，使 $a_{x}$ 与 $a_{m}$ 互换冒泡符合题意，且比当前方案花费次数更优（如果要 $4$ 个元素互换，那么必然比 $2$ 个元素互换花费次数更多），与假设矛盾，则可以证得该结论。
至于变化的数更多的情况，依次推理即可证得。

实现解析

暴力（30.5 pts）

假令 $a_{x}$ 与 $a_{m}$ 交换冒泡，最小花费 $m-x$ 的次数。
那么便可枚举 $a_{i}(k+1\le i\le n)$，找的最大的 $j$ 使得 $a_{i}>a_{j}(1\le j\le k)$。
其中 $i$ 从小到大枚举，$j$ 则从大到小枚举。
然后在此等条件下，$ans=\min(i-j)$。
笔者现提供一种暴力优化wtcl 不会打正解：
枚举时，如果当前最优答案的 $i$ 为 $i_{0}$ 且 $p>i_{0},a_{i_{0}}\ge a_{p}$，则可以跳过 $p$ 寻找下一个 $i$。（$i$ 的含义与上同）。
同理，对于 $j$ 也可记录最优答案 $j_{0}$，则每次寻找下一个 $j$ 的范围为 $j_{0}<j\le k$。
理论上时间复杂度可从 $O(n^{2})$ 优化到 $O(m^{2})(0<m\le n)$。（然鹅好像没什么卵用）。
贴一下贪心暴力部分代码。

Code

l = 0, r = n + 1;
for(int i = k + 1; i <= n; ++ i)
{
    if(a[r] >= a[i]) continue;
    for(int j = k; j > l; -- j)
    {
        if(i - j > ans) break;
        if(a[j] < a[i])
        {
            r = i, l = j;
            break;
        }
    }
    ans = r - l;
}

二分（100 pts）

不难发现，在寻找 $j$ 时，本质上是寻找最后一个比 $a_{i}$ 小的 $a_{j}$。
那么先求一遍 $a_{1}$ 到 $a_{k}$ 后缀最小值，我们发现，现在的后缀最小值满足单调性，那么就可以高高兴兴地套上二分来求最后一个满足条件地后缀最小值的位置了。
那么再用二分维护一下，期望 $O(n\log_{2}{n})$。

AC代码

贴上 AC 链接：link（跑得有点慢）

Code

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#define put putchar
#define max(a, b) a > b ? a : b
#define min(a, b) a < b ? a : b
using namespace std;

const int N = 4e5 + 10;
const int INF = 1e9;
const int mod = 1e9 + 7;

int n, k;
int a[N];
int ans = INF, l, r;
int sum[N];

inline long long read(){
    long long res = 0, f = 1;
    char c = getchar();
    while(! isdigit(c)){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
    return res * f;
}
inline void write(long long x){
    if(x >= 10) write(x / 10);
    put(x % 10 + 48);
    return ;
}
inline void print(long long x){
    if(x < 0) x = -x, put('-');
    write(x);
    return ;
}

int change(int x)
{
    if(sum[1] >= x) return 0;
    int l = 1, r = k, mid;
    int res;
    while(l <= r)
    {
        mid = l + r >> 1;
        if(sum[mid] >= x) r = mid - 1;
        else l = mid + 1, res = mid;
    }
    return res;
}

bool tp()
{
    if(n == k) return true;
    int mina = INF, maxa = -INF;
    for(int i = 1; i <= k; ++ i)
        mina = min(mina, a[i]);
    for(int i = k + 1; i <= n; ++ i)
        maxa = max(maxa, a[i]);
    if(maxa <= mina) return true;
    return false;
}

int main()
{
    memset(sum, 0x3f3f3f3f, sizeof sum);
    n = read(), k = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    for(int i = k; i ; -- i)
        sum[i] = min(a[i], sum[i + 1]);
    if(tp())
    {
        print(-1);
        return 0;
    }
    int w;
    for(int i = k + 1; i <= n; ++ i)
    {
        w = change(a[i]);
        if(! w) continue;
        ans = min(ans, i - w);
    }
    print(ans);
    return 0;
}

后记

懒得想了，就只给出一种暴力优化与二分思路。
我觉得就以各位 dalao 的实力，应该能做出来更快做法。
（其实正解是二分，但是 Split_shadow 巨佬竟然用线段树过了？）
—— Fated_Shadow