Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

二分加贪心过了。但是500k啊,有什么更快的更省的算法啊??

Posted by kamel52045386 at 2007-10-18 23:20:09 on Problem 2782
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator