第21次CSP认证题目.pdfVIP

第21次CSP认证题⽬ ⼀、//第⼀题签到题 #include bits/stdc++.h using namespace std ; int sum= ; int main(){ int N;scanf(%d,N); for (int i= ;iN;i++){ int a ,b;scanf(%d%d,a,b); sum +=a*b; } if(sum= ) printf(%d,sum); else printf(0); return ; } ⼆、第⼆题 快排+前缀和+细节处理 //期末预测之最佳阈值 关注点： 使⽤前缀和的时候，统计前n-1个数字⾥⾯的0的数⽬，统计后⾯的数字中的1的个数，但是如果有相同的数字的时候，只能统计第⼀个数 字，后⾯的所有都不再准确。 举例如下： /* 输⼊： 5 5 0 5 0 5 0 5 0 5 0 输出： 5 */ 上述例⼦，第⼀个5的统计，可以得到：0+0 第⼆个5的统计，可以得到：1+0 第三个5的统计，可以得到：2+0以此类推，所以遇到同样的数字往后跳 #include bits/stdc++.h using namespace std ; const int N=100010 ; int v[N],p[N]; int s0[N],s1[N]; void qsort (int l,int r,int q[]) if(l=r) return ; int i =l-1,j=r+1,x=q[l+r1]; while(ij) do i++;while(q[i]x); do j-- ;while(q[j]x); if(ij) swap(q[i],q[j]); swap(p[i],p[j]); } } qsort (l,j ,q),qsort (j+1,r,q); } int main() int n ;scanf(%d,n); for (int i=1;i=n;i++) scanf(%d %d,v[i],p[i]); } qsort (1,n,v); for (int i=1;i=n;i++) if(p[i]==0) s0 [i]=s0[i-1]+1; s1 [i]=s1[i-1]; }else s1 [i]=s1[i-1]+1; s0 [i]=s0[i-1]; } } int nmax =0,maxv=v[1]; int kk =0; for (int i=1;i=n;i++) while(v[i]==v[i-1]i+1=n) i++; int sum =s0[i-1]; sum +=s1[n]-s1[i-1]; if(sum=nmax) maxv =v[i]; nmax =sum ; } } printf(%d,maxv); return 0; }