UVALive 4977 Enter The Dragon

UVALive_4977

    一个贪心的思路就是我们每次喝水的时间应该尽量靠前，同时时间不能早于之间降水的时间，于是可以用线段树找到区间内第一个满足要求的点即可。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 1000010
#define INF 0x3f3f3f3f
int N, M, D, min[4 * MAXD], t[MAXD], pre[MAXD];
void update(int i)
{
    for(; i ^ 1; i >>= 1)  min[i >> 1] = std::min(min[i], min[i ^ 1]);    
}
void init()
{
    int i;
    scanf("%d%d", &N, &M);
    for(D = 1; D < M + 2; D <<= 1);
    memset(min, 0x3f, sizeof(min[0]) * 2 * D);
    for(i = 1; i <= M; i ++)
    {
        scanf("%d", &t[i]);
        if(t[i] == 0) min[D + i] = i, update(D + i);
    }
}
int query(int x, int y)
{
    int i = D + x - 1, j = D + y + 1, ans = INF;
    for(; i + 1 != j; i >>= 1, j >>= 1)
    {
        if(~i & 1) ans = std::min(ans, min[i ^ 1]);
        if(j & 1) ans = std::min(ans, min[j ^ 1]);    
    }
    return ans;
}
void solve()
{
    int i, x, flag;
    memset(pre, 0, sizeof(pre[0]) * (N + 1));
    for(i = 1; i <= M; i ++)
        if(t[i])
        {
            int x = query(pre[t[i]] + 1, i - 1);
            if(x == INF)
            {
                printf("NO\n");
                return ;    
            }
            t[x] = -t[i], min[D + x] = INF, update(D + x);
            pre[t[i]] = i;
        }
    printf("YES\n");
    flag = 0;
    for(i = 1; i <= M; i ++)
        if(t[i] <= 0)
        {
            flag ? printf(" ") : flag = 1;
            printf("%d", -t[i]);
        }
    printf("\n");
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        init();
        solve();    
    }
    return 0;    
}