ARC163B

这道题，我想出了一种只对$A_1\le A_2$成立的做法，即：计算$i\ge 3$后大于$A_2$的$A_i$，要被A1~A2包含的代价放在数组u[]里，小于$A_1$的$A_i$，要被包含的代价放在数组d[]里，然后把u[] d[]从小到大排序，再调整A1A2。于是当某一个$u_i$被包含时，所有$j < i$的$u_j$都已经被包含，$d$同理。设$m'$为m减掉已经满足$A_1\le A_i\le A_2$的数的个数，然后就有$\mathrm{ans} = \mathrm{min} _{i + j = m'}[u_i + d_j]$.

经测试这个做法可以通过所有$A_1\le A_2$的点。

但神奇的事情来了，我发现这道题有16个点不满足这个条件，而我的做法却只WA了6个点，所以我猜想这种做法可能对于$A_1> A_2$的情况也有一定的正确性。所以我很好奇，为什么这个做法能通过一部分$A_1> A_2$的点？该做法经过一些修正能否通过本题？

附上代码和记录。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200005, I = 0x3f3f3f3f;
int a[N];
int d[N], u[N], cd, cu;
int alr;
int n, m, ms;
int ans = 1e18;
signed main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%lld", &a[i]);
    }
    for(int i = 3; i <= n; ++i)
    {
        if(a[i] > a[2])
        {
            u[++cu] = a[i] - a[2];
        }
        if(a[i] < a[1])
        {
            d[++cd] = a[1] - a[i];
        }
        if(a[1] <= a[i] && a[i] <= a[2])
        {
            ++ms;
        }
    }
    sort(u + 1, u + cu + 1);
    sort(d + 1, d + cd + 1);
    m -= ms;
    if(m <= 0) ans = 0;
    int j;
    for(int i = 0; i <= min(m, cu); ++i)
    {
        j = m - i;
        if(j > cd) continue;
        ans = min(ans, u[i] + d[j]);
    }    
    printf("%lld", ans);
    return 0;
}

仅有6个点没有通过

特判使得A1>A2就RE，共RE 16个点