首页 > 其他 > 详细

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

时间:2020-05-20 13:41:34      阅读:75      评论:0      收藏:0      [点我收藏+]

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

t组测试样例,n个糖糖,发功次数m,已知组号ai和能力值bi;发功时间ci(b1到bci都会加1);

当到了i的时候,判断j能不能被消灭 j < i, 能力值 bj < bi, i和j不属于同一组

 

从后往前,分别记录两组的最大值(max比当前大,说明可以消灭)

 

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e4 + 10;
int t,n,m,max0,max1;
struct node{
    int a,b;
}e[maxn];
int c[maxn];
int cnt;
signed main() {
   // freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
            cin >> e[i].a >> e[i].b;
        memset(c,0,sizeof(c));
        for(int i = 1; i <= m; i++) {
            int x;
            cin >> x;
            c[x]++;
        }
        for(int i = n; i >= 1; i--){
            c[i] += c[i + 1];
            e[i].b += c[i];
        }
        max0 = max1 = cnt = 0;
        for(int i = n; i >= 1; i--){
            if(!e[i].a){
                max0 = max(max0,e[i].b);
                if(max1 > e[i].b)
                    cnt++;

            }else{
                max1 = max(max1,e[i].b);
                if(max0 > e[i].b)
                    cnt++;
            }
        }
        cout << n - cnt << endl;
    }
    return 0;
}

 

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

原文:https://www.cnblogs.com/xcfxcf/p/12922814.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!