試題

糖糖別胡說，我真的不是簽到題目

時間限制：C/C++ 2秒，其他語言4秒
空間限制：C/C++ 131072K，
其他語言262144K 64bit
IO Format:%lld

題目描述

從前，有n只萌萌的糖糖，他們分成了兩組一起玩游戲。他們會排成一排，第i只糖糖會隨機得到一個能力值bi。從第i秒的時候，第i只糖糖就可以消滅掉所有排在他前面的和他不是同一組的且能力值小于他的糖糖。

為了使游戲更加有趣，糖糖的爸爸，嬌姐，會發(fā)功m次，第i次發(fā)功的時間為ci，則在第ci秒結束后，b1,b2,…,bci都會增加1.

現(xiàn)在，嬌姐想知道在第n秒后，會有多少只糖糖存活下來。

輸入描述:

第一行只有一個整數T（T<6），表示測試數據的組數。
第二行有兩個整數n,m。表示糖糖的個數以及嬌姐發(fā)功的次數。（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次發(fā)功的時間.(1<=ci<=n)

輸出描述:

總共T行，第i行表示第i組數據中，糖糖存活的個數。

示例1
輸入

1 4 3 0 3 1 2 0 3 1 1 1 3 4

輸出

3

題解：

我們先想想一個糖糖能活下來需要什么條件？
就是在它后面不存在一個比他的大的且不在一個組
兩個要求：不能比他大且不在一組
這樣我們其實就可以從后往前掃描，（因為這樣掃描過的，不會再被消滅，我們就不用再管了），來維護當前位置往后每一組糖糖的最大值，然后比較，如果比這個位置大，這個位置的糖糖不就被消滅了

還有個發(fā)功問題（頭大）
發(fā)功后并不是都+1，而是前ci個人+!,前ci個人之間的相對大小并沒發(fā)生改變，所以不影響第ci個糖糖在第ci秒消滅他前面的糖糖。
而第ci之后的并沒有+1，那咋辦？我們可以用每個人最后的能力值來判斷到底能不能存活
我們先求出每個糖糖最后的能力值，倒著判斷每個糖糖是否能存活，用前綴和優(yōu)化

具體看代碼：

#include<bits/stdc++.h> #define forr(n) for(int i=1;i<=n;i++) typedef long long ll; using namespace std; const ll maxn=1e5+2; ll t; ll n,m; ll s[maxn]; ll a[maxn]; ll b[maxn]; ll pre[maxn]; ll sum,maxx,maxx1; int main(){cin>>t;while(t--){cin>>n>>m;forr(n){cin>>a[i]>>b[i]; }forr(m){ll w;cin>>w;s[w]++;}for(int i=n;i>=1;i--) pre[i]=pre[i-1]+s[i];for(int i=n;i>=1;i--){b[i]+=pre[i];if(!a[i]){if(b[i]>maxx1) maxx1=b[i];//更新0隊伍的最大值 if(b[i]<maxx) sum++;}else{if(b[i]>maxx) maxx=b[i];//更新1隊伍最大值 if(b[i]<maxx1) sum++; }}cout<<n-sum;}return 0; }/* 1 4 3 0 3 1 2 0 3 1 1 1 3 4 */ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的牛客网【每日一题】4月21日题目精讲 糖糖别胡说，我真的不是签到题目的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。