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

哪位大哥帮忙看一下,我用贪心,一直WA

Posted by suibian at 2005-07-13 10:56:33 on Problem 2465
#include <iostream.h>
//#include <fstream.h>//////////
#define MAX 10000

struct Node{
    int dis;
    int price;
};

int main()
{
    Node st[102];
    bool flag,found;
    int left,cnt=0,dis,delta;
    int tot=0,i,j,a,b,d;
    //ifstream cin("in.txt");////////////
    //ofstream cout("out.txt");/////////

    //input data
    cin>>dis;
    cin>>a>>b;
    if(a!=0)
    {
        st[0].dis=0;
        st[0].price=MAX;
        cnt=1;
    }
    st[cnt].dis=a;
    st[cnt].price=b;
    cnt++;
    while(cin>>st[cnt].dis>>st[cnt].price && st[cnt].dis<=dis)
        cnt++;
    st[cnt].dis=dis+100;
    st[cnt].price=0;
    //check existence of solution
    left=100;
    flag=true;
    for(i=0;i<cnt;i++)
    {
        if(i==0 && st[0].price==MAX && left<st[1].dis)
            flag=false;
        if(flag && st[i].dis+200<st[i+1].dis)
            flag=false;
    }
    //find a solution
    if(flag)
	{
		for(i=0;i<cnt;)
		{
			found=false;
			if(i==0 && st[0].price==MAX)
               delta=left;
            else delta=200;
            //找第一个油价比它低的gas station 
			for(j=i+1;j<=cnt && st[j].dis<=st[i].dis+delta;j++)
					if(st[j].price<st[i].price)
					{
                        found=true;
						break;
					}
			if(found)//找见了 
			{
				d=st[j].dis-st[i].dis;
				if(d>left)
				{
					//cout<<i<<"  "<<d-left<<"  "<<st[i].price<<endl;////////
					tot+=(d-left)*st[i].price;
					left=0;
				}
				else
                    left-=d;
                i=j;
			}
			else//油价都比它高 
			{
				//cout<<i<<"   "<<200-left<<"  "<<st[i].price<<endl;////////
				tot+=(200-left)*st[i].price;
				left=200-(st[i+1].dis-st[i].dis);
				i++;
			}
		}
		cout<<tot<<endl;
	}
    else
        cout<<"Impossible";
    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