题解P7514

AuCloud · 2021-04-12 20:52:35 · 题解

来自一个考场上被自己一顿阴间操作把D1T1正解文件搞没了的sb

提供思路，不一定正确，欢迎各大佬hack（但是过了民间数据

对所有的值按大小排序，不论 a 面 b 面

记录每个值对应是 a 面或者 b 面

于是现在我们得到了一个长度为 2N 的序列。

显然我们的答案就是这个序列的某个子序列两端的差值

具体求可以用双指针——我们可以删除前面一段和后面一段，要求是

• 删除的 a 面总数不能超过要求

• 不能同时删除同一张卡的两面

对于第一条就拿个变量动态记录一下删了多少个就好

第二条开个桶维护就好

总时间复杂度O(N\log N)，瓶颈在排序

代码如下

#include <bits/stdc++.h>
using namespace std;
struct hehe{
    long long a, num;
    int op;
    bool operator < (hehe b) const
    {
        return a < b.a;
    }
}a[2000001];
bool used[2000001];
int main()
{
    // freopen("card3.in", "r", stdin);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].a);
        a[i].num = i;
        a[i].op = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[n + i].a);
        a[i + n].num = i;
        a[i].op = 1;
    }
    sort(a + 1, a + n * 2 + 1);
    int l = 0, r = n * 2 + 1, now = 0;
    while(!used[a[l + 1].num] && now + a[l + 1].op <= k) now += a[l + 1].op, used[a[l + 1].num] = 1, l++;
    while(!used[a[r - 1].num] && now + a[r - 1].op <= k) now += a[r - 1].op, used[a[r - 1].num] = 1, r--;
    long long ans = 1000000000000;
    while(l >= 0)
    {
        ans = min(a[r - 1].a - a[l + 1].a, ans);
        used[a[l].num] = 0;
        now -= a[l].op;
        l--;
        while(!used[a[r - 1].num] && now + a[r - 1].op <= k) now += a[r - 1].op, used[a[r - 1].num] = 1, r--;

    }
    cout << ans << endl;
}

碎碎念：亲手把自己送出省队，我现在心态良好