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

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

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

链接:https://ac.nowcoder.com/acm/problem/14583
来源:牛客网

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format: %lld
题目描述
从前,有n只萌萌的糖糖,他们分成了两组一起玩游戏。他们会排成一排,第i只糖糖会随机得到一个能力值bi。从第i秒的时候,第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。

为了使游戏更加有趣,糖糖的爸爸,娇姐,会发功m次,第i次发功的时间为ci,则在第ci秒结束后,b1,b2,.....,bci都会增加1.

现在,娇姐想知道在第n秒后,会有多少只糖糖存活下来。

输入描述:
第一行只有一个整数T(T<6),表示测试数据的组数。
第二行有两个整数n,m。表示糖糖的个数以及娇姐发功的次数。(1<=n<=50000,1<=bi<=1000000)
第三行到n+2行,每行有两个整数ai,bi,表示第i只糖糖属于那一组以及他的能力值。(0<=ai<=1,1<=bi<=1000000)
第n+3行到第n+m+2行,每行有一个整数ci,表示GTW第i次发功的时间.(1<=ci<=n)
输出描述:
总共T行,第i行表示第i组数据中,糖糖存活的个数。
示例1
输入
1 4 3 0 3 1 2 0 3 1 1 1 3 4

输出
3

题解:
这道题目真的。。。。。。果然不是签到题。。。。。。
当时写第一遍的时候就直接写到前缀和的基本操作,后面就没(不)有(会)再(写)弄(了)。今天看了别人的题解,照着把后面最有含金量的四行代码补上,换成scanf就ac了。(QAQ这个scanf啊。。。。真的是。。。。。)
下面就是复述了。ai是不是会死取决于后面有没有功力更高的对手aj,我们知道ai和aj的功力和发功对应的前缀和。而然我们已经做好了前缀和,那就发功的影响只需要计算前缀和的差值,也就是b[i-1]-b[j-1]。所以如果ai会被aj杀死,那么a[i]+b[j-1]-b[i-1]<a[j];把i、j移到同一侧,也就是a[i]-b[i-1]<a[j]-b[j-1];又由于我们知道如果不是最强的都能杀死他,那么最强的也一定可以。问题就变得非常简单了,只需要维护两队各自的最强者即可。

代码:
using namespace std;
#include <bits/stdc++.h>
#define int long long
int a[50005][4],b[50005],Max[2];
int inf=0x3f3f3f3f;
signed main (void)
{
int t;cin>>t;
while (t--)
{
memset (a,0,sizeof a);
memset (b,0,sizeof b);
Max[0]=Max[1]=-inf;
int n,m;cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i][0]>>a[i][1];
}
for (int i=1;i<=m;i++)
{
int x;cin>>x;
b[x]++;
}
for (int i=1;i<=n;i++)
{
b[i]+=b[i-1];
cout<<b[i];
}
int cnt=0;
for (int i=n;i>0;i--)
{
int sum=Max[a[i][0]^1];
if (sum<=a[i][1]-b[i-1]) cnt++;
Max[a[i][0]]=max(Max[a[i][0]],a[i][1]-b[i-1]);
}
cout<<cnt<<'\n';
}
}

全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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