题目大意
Alice
有 \(n\) 张卡牌,第 \(i(1≤i≤n)\)张卡牌的正面有数字 \(a_i\),背面有数字 \(b_i\),初始时所有卡牌正面朝上。
现在 Alice
可以将不超过 \(m\) 张卡牌翻面,即由正面朝上改为背面朝上。
Alice
的目标是让最终朝上的 \(n\) 个数字的极差(最大值与最小值的差)尽量小。
请你帮 Alice
算一算极差的最小值是多少。
解题思路
似乎是省选 \(D1T1\),不过好像也没那么难。
对于数字考虑,极差最小就是对于排序之后的数组中,取一个长度最短的区间。
我们把 \(a_i\) 和 \(b_i\) 都放进去排序,取 \(n\) 张牌至少出现一次且反面向上的不超过 \(m\) 张的区间,用双指针维护即可(我们可以通过双指针删除前面一段和后面一段,这样直接判断中间那一段就好了)。
时间复杂度 \(\mathcal{O}(n)\)。
AC CODE
#include <bits/stdc++.h>
#include <array>
using namespace std;
const int maxn = 2e6 + 5;
inline int read()
{
char c = getchar();
int x = 0;
bool f = 0;
for (; !isdigit(c); c = getchar())
{
f ^= !(c ^ 45);
}
for (; isdigit(c); c = getchar())
{
x = (x << 1) + (x << 3) + (c ^ 48);
}
if (f)
{
x = -x;
}
return x;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
struct abc
{
int val;
int id;
int flag;
};
int n, m, x, ans = INT_MAX;
int l, r, now;
array<bool, maxn> vis;
array<abc, maxn> e;
bool cmp(abc x, abc y)
{
return x.val < y.val;
}
bool check(int x)
{
return (!vis[e[x].id] && (now + e[x].flag <= m));
}
void add(int x)
{
now += e[x].flag;
vis[e[x].id] = true;
}
void del(int x)
{
now -= e[x].flag;
vis[e[x].id] = false;
}
signed main()
{
n = read();
m = read();
for (int i = 1; i <= n; i++)
{
x = read();
e[i].val = x;
e[i].id = i;
e[i].flag = 1;
}
for (int i = 1; i <= n; i++)
{
x = read();
e[i + n].val = x;
e[i + n].id = i;
e[i + n].flag = 0;
}
sort(e.begin() + 1, e.begin() + n * 2 + 1, cmp);
l = 0;
r = n * 2 + 1;
now = 0;
while (check(l + 1))
add(++l);
while (check(r - 1))
add(--r);
while (l)
{
ans = min(ans, e[r - 1].val - e[l + 1].val);
del(l--);
while (check(r - 1))
add(--r);
}
write(ans);
return 0;
}