题目
题意
给定n个任务和艾米的智商q,艾米要按顺序处理这n个任务,每个任务有难度值a[i]。
对于每个任务,艾米可以选择处理,也可以选择不处理。
如果艾米当前的智商q大于等于任务a[i],则艾米可以直接处理该任务,智商不受任何影响。
如果艾米当前的智商q小于任务a[i],则艾米会自我怀疑,虽然可以完成任务,但智商会降一。
现要求,在保持智商为非负数的情况下,艾米最多能处理多少个任务。
思路
典型的二分加贪心
贪心时,对于当前需要处理num个任务数,处理不了的,能不处理的直接pass(保留智商值)。
详见代码
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 500010;
int n, q;
int a[maxn];
char s[maxn], tmp[maxn];
bool check(int num) {
int skip = n - num;// 最多能跳过多少个任务
int tmpq = q;// 当前智商值
for (int i = 0; i < n; ++i) {
if (tmpq <= 0) {// 智商值不足
tmp[i] = '0';
continue;
}
if (a[i] <= tmpq) {// 当前任务能直接处理的
tmp[i] = '1';
--num;
continue;
}
if (skip) {// 任务难度高,但能skip的
tmp[i] = '0';
--skip;
} else {// skip不了,则硬肝了
tmp[i] = '1';
--num;
--tmpq;
}
}
return num <= 0;
}
void solve() {
scanf("%d%d", &n, &q);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
if (q >= n) {
for (int i = 0; i < n; ++i) {
s[i] = '1';
}
} else {
int l = 0, r = n, m;
while (l < r) {
m = (l + r + 1) >> 1;
if (check(m)) {
l = m;
} else {
r = m - 1;
}
}
// printf("res : %d\n", l);// debug
check(l);
for (int i = 0; i < n; ++i) {
s[i] = tmp[i];
}
}
s[n] = '\0';
printf("%s\n", s);
return;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
}