牛客演算法NC14583
鏈接：https://ac.nowcoder.com/acm/problem/14583
來源：牛客網
題目：
從前，有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組資料中，糖糖存活的個數，
樣例：
思路：
考慮到題目看起比較復雜，一定要好好的讀題，首先很明顯，在ci秒加上去的能力值是不影響前面的，因為是從b1一直加到bci，是一個區間加上1，因此可以考慮差分法，即在區間的開頭和結尾做操作，然后對于對應區間進行維護即可，免去處理復雜的c[i]，
#include<bits/stdc++.h>
using namespace std;
int a[50010],b[50010],c[50010];
int main()
{
int n,m;
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
memset(c,0,sizeof c); //初始化，很重要
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(int i=1;i<=m;i++)
{
int ci;
cin>>ci;
c[1]++; //對于差分陣列，對最前和最后+1個數進行操作
c[ci+1]--;
}
for(int i=1;i<=n;i++)
{
c[i]=c[i]+c[i-1]; //維護c[i]陣列
b[i]=b[i]+c[i]; //把b[i]算出來
}
int max0=-1,max1=-1,ans=0;
for(int j=n;j>=1;j--)
{
if(a[j]==0) max0=max(max0,b[j]); //分別找隊1與隊0的最大值
else max1=max(max1,b[j]);
if(a[j]==0 && b[j]>=max1) ans++; //如果后者大于前者，則加1
if(a[j]==1 && b[j]>=max0) ans++;
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/271472.html
標籤：其他
上一篇：手寫深拷貝及深拷貝理解
下一篇：黑科技網站第三彈 懷舊游戲集錦