Chinaunix首页 | 论坛 | 博客
  • 博客访问: 54276
  • 博文数量: 9
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 80
  • 用 户 组: 普通用户
  • 注册时间: 2014-07-16 22:03
个人简介

Small thing follow your head, big thing follow your heart.

文章分类

全部博文(9)

文章存档

2015年(4)

2014年(5)

我的朋友

分类: C/C++

2014-11-18 21:51:05

例题:POJ2431(xepedition)
题意:一辆卡车要行驶L单位距离。最开始时,卡车上有P单位汽油,每向前行驶1单位距离消耗1单位汽油。如果在途中车上的汽油耗尽,卡车就无法继续前行,即无法 到达终点。途中共有N个加油站,加油站提供的油量有限,卡车的油箱无限大,无论加多少油都没问题。给出每个加油站距离终点的距离和能够提供的油量,问卡车 从起点到终点至少要加几次油?如果不能到达终点,输出-1。

思路:在经过加油站i时,往优先队列里加入Bi;当燃料空是,如果队列空,则无法到达终点(return -1),否则取出优先队列中的最大元素,并用来给卡车加油!

代码:

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. using namespace std;

  5. #define MAX_N 10000

  6. int len = 0;
  7. int p_oil = 0;
  8. int n_station = 0;
  9. int A[MAX_N + 1] = {0};
  10. int B[MAX_N + 1] = {0};

  11. void solve()
  12. {
  13.     A[n_station] = len;
  14.     B[n_station] = 0;
  15.     n_station++;              
  16.     
  17.     priority_queue<int> que;                //优先队列,这里还不懂,值越大越优先么在这里?

  18.     int ans = 0;           
  19.     int position = 0;       
  20.     int tank = p_oil;       
  21.     int next_d = 0;          

  22.     for (int i = 0; i < n_station; i++)
  23.     {
  24.         next_d = A[i] - position;

  25.         while (tank - next_d < 0)        //have not enough oil to next target
  26.         {
  27.             if (que.empty())
  28.             {
  29.                 puts("-1");
  30.                 return;
  31.             }

  32.             tank += que.top();
  33.             que.pop();
  34.             ans++;                        //add one to ans;
  35.         }

  36.         tank -=next_d;
  37.         position = A[i];
  38.         que.push(B[i]);
  39.     }

  40.     printf("have to add %d times!\n", ans);
  41. }

  42. int main(void)
  43. {
  44.     printf("how many gas station?\n");
  45.     scanf("%d", &n_station);
  46.     printf("how long distance?\n");
  47.     scanf("%d", &len);
  48.     printf("how many oil now?\n");
  49.     scanf("%d", &p_oil);

  50.     printf("请输入每个车站的距离!\n");
  51.     for (int i = 0; i < n_station; i++)
  52.     {
  53.         scanf("%d", &A[i]);
  54.     }

  55.     printf("请输入每个车站能提供!\n");
  56.     for (int j = 0; j < n_station; j++)
  57.     {
  58.         scanf("%d", &B[j]);
  59.     }

  60.     solve();

  61.     return 0;
  62. }

运行结果:

阅读(3156) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~