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