当前位置：网站首页>codeforce：A. Doremy‘s IQ【反向贪心】

codeforce：A. Doremy‘s IQ【反向贪心】

2022-07-17 18:13:00 【白速龙王的回眸】

在这里插入图片描述

分析

所谓贪心，要么正向要么反向
反正都是on的

这道题而言，我们知道最后的iq肯定是最低的，不妨从0开始
从最后开始反序贪心
如果当前的iq都大于ai，就直接设置成1
如果当前的iq小于一开始的q，让当前iq+1，再设置成1
最后情况就是iq已经等于一开始的q，但还是ai大于iq，但就无可奈何

ac code

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n, q = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = ['0'] * n


    rest_q = 0
    # reverse + greedy
    for i in range(n - 1, -1, -1):
        # greedy
        if rest_q >= a[i]:
            b[i] = '1'
        # can add
        elif rest_q < q and a[i] > rest_q:
            rest_q += 1
            b[i] = '1'
        # do nothing
        else:
            pass

    print(''.join(b))