[每日一题] 4.21 糖糖别胡说,我真的不是签到题目
糖糖别胡说,我真的不是签到题目
http://www.nowcoder.com/questionTerminal/9d5b203a30bc4e7b85f1838d60cf2236
题意:
解法:
时间复杂度:
std:
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 500005; struct node{ int x; ll y; }a[maxn]; ll b[maxn]; int main() { int t,n,m,x; scanf("%d",&t); while(t--){ memset(b,0,sizeof(b)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d%lld",&a[i].x,&a[i].y); for(int i=1;i<=m;i++)scanf("%d",&x),b[x]++; for(int i=n;i>=1;i--)b[i] += b[i+1] , a[i].y += b[i]; int cnt = 0; ll max0 = 0, max1 = 0; for(int i=n;i>=1;i--){ if(a[i].x == 0){ max0 = max(max0 , a[i].y); if(max1 > a[i].y) cnt++; } else{ max1 = max(max1 , a[i].y); if(max0 > a[i].y) cnt++; } } printf("%d\n",n - cnt); } return 0; }
acm菜鸡日常 文章被收录于专栏
一般写一些打过的比赛题解以及不会的算法