P1016 旅行家的预算

唔。。这是我当初好久好久之前做过的一道题，然后，就压仓库了？？

前两天正好听到srj提到这道题，就正好拿出来做一下

那么还是一个不太难想的贪心，我也不知道为什么之前只有50分。。

 1 #include <bits/stdc++.h>
 2 double D0,C,D,cost,left;
 3 struct node
 4 {
 5     double d,p;
 6 }s[8];
 7 int n;
 8 bool cmp(node a,node b){return a.d<b.d;}
 9 int main()
10 { 
11     scanf("%lf%lf%lf%lf%d",&D0,&C,&D,&s[0].p,&n);
12     s[n+1].d=D0;
13     for(int i=1;i<=n;i++)
14     {
15         scanf("%lf%lf",&s[i].d,&s[i].p);
16         if(s[i].d-s[i-1].d>C*D)//中间有一段路加满油也到不了下个节点
17         {
18             printf("No Solution");
19             return 0;
20         }
21     }
22     std::sort(s+1,s+1+n,cmp);
23     for(int i=0;i<=n+1;)
24     {
25         int j,k;
26         for(j=k=i+1;j<=n;j++)//若直达终点，j++后j为n+1而不是n+2
27         {
28             k=s[j].p<=s[k].p?j:k;//范围内最小花费
29             if(s[j].p<=s[i].p||s[j+1].d-s[i].d>C*D)break;//找到下一个比当前节点便宜的节点或者到不了下个节点
30         }
31         if(s[j].p>s[i].p)//策略2
32         {
33             cost+=(C-left)*s[i].p,left=C-(s[k].d-s[i].d)/D;
34             i=k;
35         }
36         else
37             cost+=s[i].p*((s[j].d-s[i].d)/D-left),i=j,left=0;//策略1
38     }
39     printf("%.2lf",cost);
40     return 0;
41 }

lalala