NC14583 糖糖别胡说

糖糖别胡说,我真的不是签到题目

https://ac.nowcoder.com/acm/problem/14583

题目大意

略。

题解

容易想到按秒处理。发现前 个能力值加一可以转化为后面 个能力值减一。

于是维护到当前时间为止,当前位置及后面位置能力值被削减的量。之后就是简单的用两个堆处理一下即可。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m;
int a[50005], b[50005];
int cnt[50005];
priority_queue<int, vector<int>, greater<int> > pq[2]; 
void init(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = read();
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= m; ++i)
        ++cnt[read()];
}
void solve(){
    int cur = 0;
    for (int i = 1; i <= n; ++i){
        int oppo = a[i] ^ 1;
        while (!pq[oppo].empty() && pq[oppo].top() < b[i] - cur)
            pq[oppo].pop();
        pq[a[i]].push(b[i] - cur);
        cur += cnt[i];
    }
    int ans = pq[0].size() + pq[1].size();
    printf("%d\n", ans);
    while (!pq[0].empty()) pq[0].pop();
    while (!pq[1].empty()) pq[1].pop();
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务