• 博客访问： 54276
• 博文数量： 9
• 博客积分： 0
• 博客等级： 民兵
• 技术积分： 80
• 用 户 组： 普通用户
• 注册时间： 2014-07-16 22:03

2015年（4）

2014年（5）

2014-11-18 21:51:05

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. }