| ||||||||||
| 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 | |||||||||
哪位大哥帮忙看一下,我用贪心,一直WA#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator