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

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

http://www.nowcoder.com/questionTerminal/9d5b203a30bc4e7b85f1838d60cf2236

题意:
从前,有n只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第i只糖糖会随机得到一个能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。
为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.
现在,娇姐想知道在第n秒后,会有多少只糖糖存活下来。
思路:差分,模拟。
代码:

#include<bits/stdc++.h>

using namespace std;
#define ll long long
int zu[5000005];
int val[5000005];
int cha[5000005];
int gn[5000005];
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&zu[i],&val[i]);
        for(int i=1;i<=m;i++)
            scanf("%d",&gn[i]);
        for(int i=1;i<=n;i++)
            cha[i]=val[i]-val[i-1];
        for(int i=1;i<=m;i++)
        {
            cha[1]++;
            cha[gn[i]+1]--;
        }
        for(int i=1;i<=n;i++)
            val[i]=val[i-1]+cha[i];
        int ma[2];
        ma[0]=ma[1]=0;
        int ans=0;
        for(int i=n;i>0;i--)
        {
            if(val[i]>=ma[zu[i]^1])
                ans++;
            if(val[i]>ma[zu[i]])
                ma[zu[i]]=val[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}
全部评论

相关推荐

10-14 23:01
已编辑
中国地质大学(武汉) Java
CUG芝士圈:虽然是网上的项目,但最好还是包装一下,然后现在大部分公司都在忙校招,十月底、十一月初会好找一些。最后,boss才沟通100家,别焦虑,我去年暑假找第一段实习的时候沟通了500➕才有面试,校友加油
点赞 评论 收藏
分享
09-27 14:42
已编辑
浙江大学 Java
未来未临:把浙大放大加粗就行
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务