题目大意:
一头牛从起点到终点,最开始有P升油,每走一公里漏一升油,路途上有许多加油点,油箱容量为无穷大,求能到终点的最小加油次数。
《挑战程序设计竞赛》建议首先处理输入数据,使之成为到起点的距离。
优先队列练习
用优先队列存储路过的加油点的油。每次取用最大值,这样会使加油次数尽量减少。每取出一次就ans++.
值得注意的是:需要增加距离起点为l的点,保证最后一个加油点到终点能成功走到,因为有可能存在最后的油量走不到终点的情况,所以这个是必须要加的。【WA无数次在这里。
1 #include2 #include 3 #include 4 using namespace std; 5 int n, tank, l, p, ans; 6 struct node{ 7 int l, r; 8 }a[10010]; 9 bool cmp(node a, node b){10 return a.l < b.l;11 }12 int main(){13 //freopen("1.in", "r", stdin);14 while(~scanf("%d", &n)){15 ans = 0, tank = 0;16 for(int i = 1; i <= n; i++){17 scanf("%d %d", &a[i].l, &a[i].r);18 }19 scanf("%d %d", &l, &p);20 for(int i = 1; i <= n; i++)a[i].l = l - a[i].l;21 n++;22 a[n].l = l;a[n].r = 0;23 sort(a+1,a+1+n, cmp);24 int pos = 0;25 tank = p;26 priority_queue q;27 for(int i = 1; i <= n; i++){28 int d = a[i].l - pos;29 while(tank - d < 0){30 if(q.empty()){31 //printf("-1\n");32 ans = -1;33 break;34 }35 tank += q.top();36 q.pop();ans++;37 }38 if(ans == -1)break;39 tank -= d;40 pos = a[i].l;41 q.push(a[i].r);42 }43 printf("%d\n", ans);44 }45 }