高桥和低桥 ( 代代相传刷qq + 无敌二分 )
中南oj 1335
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1335
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int h[100002],p[100002]; 8 9 int find1(int l,int r,int x) 10 { 11 int m; 12 while(l<r) 13 { 14 m=(l+r)/2; 15 if(h[m]>x) 16 r=m; 17 else l=m+1; 18 } 19 return l; 20 } 21 22 int find2(int l,int r, int x) 23 { 24 int m; 25 int ans=0; 26 while(l<=r) 27 { 28 m=(l+r)/2; 29 if(h[m]<=x) 30 { 31 if(m>ans) 32 ans=m; 33 l=m+1; 34 } 35 else 36 r=m-1; 37 } 38 return ans; 39 } 40 41 int main() 42 { 43 int i,j,m,n,t,k,a,b,d,g,pp=1; 44 while(~scanf("%d%d%d",&n,&m,&k)) 45 { 46 for(i=0;i<n;i++) 47 scanf("%d",&h[i]); 48 sort(h,h+n); 49 int d=0; 50 memset(p,0,sizeof(p)); 51 while(m--) 52 { 53 scanf("%d%d",&a,&b); 54 g=a; 55 56 int left,right; 57 left=find1(0,n-1,d); 58 right=find2(0,n-1,g); 59 //printf(" l r %d %d %d %d\n",left,right,d,g); 60 p[left]++; 61 p[right+1]--; 62 d=b; 63 } 64 int num=0,sum=0; 65 for(i=0;i<n;i++) 66 { 67 num+=p[i]; 68 if(num>=k) 69 sum++; 70 } 71 printf("Case %d: %d\n",pp++,sum); 72 } 73 return 0; 74 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。