Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
二分加贪心过了。但是500k啊,有什么更快的更省的算法啊??#include<stdio.h> #include<cstdlib> #include<algorithm> using namespace std; int p[100005]={0}; int n,l; int can(int m) { int i,j,q; j=2*m-1; for(i=0;i<j;i++) { if(j>=n) q=0; else q=p[j]; if(p[i]+q<=l) j--; else break; } if(i>=j) return 1; return 0; } int cmp(int a,int b) { return a>b; } int main() { int i,sum,low,mid,high; scanf("%d%d",&n,&l); sum=0; for(i=0;i<n;i++) { scanf("%d",&p[i]); sum+=p[i]; } sort(p,p+n,cmp); high=n; low=sum/l; while(low<high) { mid=((low+high)/2); if(can(mid)) high=mid; else low=mid+1; } printf("%d\n",low); //system("pause"); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator