4月21日 糖糖别胡说,我真的不是签到题目

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

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

题意

n个人排成一排,分成两组,第i个人属于a[i]组,每个人有一个能力值b[i],从左往右每个人在第i秒执行一次动作,可以把前面不属于自己组的且能力值小于自己的消灭。
同时有m次操作c[i],可以在第c[i]秒后把所有前面的人包括自己的能力值增加一,求第n秒后的存活人数。

题解

要找出每个人能消灭前面的人数有多少个很难,那么我们考虑第i个人会不会被消灭。做这种题首先要分析清楚随着时间的变化什么是不变的
走两个样例可以看出,如果第j个人在第j秒能消灭第i个人,那么无论第j秒后,他俩的能力值怎么变化,能力值的差值一定是不变的,换句话说,如果第j个人能消灭第i个人,那么在第j秒后,第j个人还是可以消灭第i个人。那么问题就简单了,既然随着时间的增加,结果是不变的,那么我直接跑完n秒后,再去判断有多少人存活也是一样的。处理处第n秒后所有人的能力值,记录从后往前,两个组的最大值,第i个人是否会被消灭,只需判断他的能力值和另一组的最大值的大小即可。
注意:c[i]是可以重复的。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7, mod = 1e9 + 7;
typedef long long ll;
int n, m, a[maxn], b[maxn], c[maxn];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        memset(c, 0, sizeof(c));
        for (int i = 1; i <= n; i++) scanf("%d%d", &a[i], &b[i]);
        for (int i = 1, x; i <= m; i++) scanf("%d", &x), c[x]++;
        int max1 = 0, max0 = 0, ans = n;
        for (int i = n; i >= 1; i--) c[i] += c[i + 1], b[i] += c[i];
        for (int i = n; i >= 1; i--) {
            if(a[i]) {
                max1 = max(max1, b[i]);
                ans -= (b[i] < max0);
            }
            else {
                max0 = max(max0, b[i]);
                ans -= (b[i] < max1);
            }
        }
        printf("%d\n", ans);
    }
}
每日一题 文章被收录于专栏

每日一题本菜鸡没做出来的

全部评论

相关推荐

来个厂收我吧:首先,市场侧求职我不是很懂。 但是,如果hr把这份简历给我,我会觉得求职人不适合做产品经理。 问题点: 1,简历的字体格式不统一,排版不尽如人意 2,重点不突出,建议参考star法则写个人经历 3,印尼官方货币名称为印度尼西亚卢比(IDR),且GMV690000印尼盾换算为305人民币,总成交额不高。 4,右上角的意向职位在发给其他公司时记得删除。 5,你所有的经历都是新媒体运营,但是你要投市场营销岗位,jd和简历不匹配,建议用AI+提示词,参照多个jd改一下经历内容。 修改建议: 1,统一字体(中文:思源黑体或微软雅黑,英文数字:time new romans),在word中通过表格进行排版(b站学) 2,校招个人经历权重:实习经历=创业经历(大创另算)>项目经历>实训经历>校园经历 3,请将项目经历时间顺序改为倒序,最新的放最上方。 4,求职方向不同,简历文字描述侧重点也需要不同。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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