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

一直runtime error,本人崩溃了,求教,谢谢

Posted by attens1727 at 2011-08-28 21:38:33 on Problem 2431
不过解题思路应该可以先快排后直接贪心,最坏是O(n^2)
以下是程序:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define maxn 10010

long n,P,L,ans;
struct node
{
	long dis,acq;
}fuel[maxn];

void swap(struct node *t,struct node *m)
{
	struct node tmp;
	tmp=*t;
	*t=*m;
	*m=tmp;
}
void sort(long L,long R)
{
	srand(time(NULL));
	long i=L,j=R,m=rand()%(R-L+1)+L,pick=fuel[m].dis;
	do{
		while(i<=j&&fuel[i].dis<pick) i++;
		while(i<=j&&fuel[j].dis>pick) j--;
		if(i>j) break;
		swap(&fuel[i],&fuel[j]);
		i++;j--;
	}while(i<=j);
	if(i<=R) sort(i,R);
	if(j>=L) sort(L,j);
}
void init(void)
{
	freopen("2431.in","r",stdin);
	freopen("2431.out","w",stdout);
	long i;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d%d",&fuel[i].dis,&fuel[i].acq);
	scanf("%d%d",&L,&P);
	for(i=1;i<=n;++i)
	    fuel[i].dis=L-fuel[i].dis;
    sort(1,n);
}
void solve(long begin)
{
	long i,max,x;
	if(P>=L) {printf("%d\n",ans);exit(0);}
	i=begin;max=0;x=0;
	while(fuel[i+1].dis<=P)
	{
		if(fuel[i+1].acq>max) {max=fuel[i+1].acq;x=i+1;}
		i++;
	}
	P+=max;
	if(max==0) {printf("-1\n");exit(0);}
	ans++;
	solve(x);
}
int main()
{
	init();
	ans=0;
	solve(0);
	return 0;
}

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