寒假思维训练day20

更新一道1600的反向贪心

题意：

有n场比赛，且小明的智商是m，每场比赛需要的智商是,当时, 可以直接看题，当时，需要智商m减1才能看这道题，当智商为0不能继续往下看题，问最多能看多少题

题解：

1、已知

2、

当时，我们直接可以全部都看，答案为n。

当时，假设最优解为：, 我们来构造出一个等价的解，我们此时来看最后一次选择, 当看 != n时，必然要有, 那么此时因为最优解当中不存在n, 显然m恰好为1, 那我们不妨不选,选择,此时我们的解可以构造成, 在此基础上我们进行贪心，往前贪心，因为到时我们的智商 >= 1,那我们从后往前倒推，定初始值sum = 0, 当sum >= , 我们取走i, 只要sum < m, 我们取走当前位，sum += 1,因为当尽可能多的取走可以使得sum 尽可能更早地逼近m, 对前面的选择更有利 。

代码 (cpp)：

#include <bits/stdc++.h>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std; 
const int N = 2e5 + 10; 
const int inf = 0x3f3f3f3f; 
int n, m;  
int a[N]; 
int cn[N]; 
void solve() {
    cin >> n >> m; 
    for(int i = 1; i <= n; i ++ ) cin >> a[i]; 
    vector<int> ans(n + 1, 0); 
    int t = 0; 
    for(int i = n; i >= 1; i -- ) {
        if(t >= a[i]) ans[i] = 1; 
        else if(t < m) t ++, ans[i] = 1; 
    }
    for(int i = 1; i <= n; i ++ ) cout << ans[i]; 
    cout << endl; 
    
}
signed main() {
    int ts; 
    cin >> ts; 
    while(ts -- ) solve(); 
    
    return 0; 
}
/* 

1
5 4
5 1 5 1 4 3 

*/