poj（2431）（优先队列http://poj.org/problem?id=2431）

向右看齐 2022-08-27 07:58 49阅读 0赞

题目：http://poj.org/problem?id=2431

题意：有n个加油站在一条直线上，每个加油站最多可以加多少油，以及加油站的位置到终点的距离，假设汽车邮箱容量无限，以及初始的油量，求能不能到终点及最少的加油次数。

分析：优先队列模拟题意，油足够的话向前走，油不够的时候从走过的路里面选择可以加油最多的地方加油！

代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <queue>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 12000;
  7. struct Node
  8. {
  9.     int lis,pro;
  10. };
  11. Node a[N];
  12. int comp(Node a,Node b)
  13. {
  14.     if(a.lis!=b.lis)
  15.         return a.lis<b.lis;
  16. }
  17. int main()
  18. {
  19.     priority_queue<int> v;
  20.     int n;
  21.     while(~scanf("%d",&n))
  22.     {
  23.         for(int i=1;i<=n;i++)
  24.             scanf("%d%d",&a[i].lis,&a[i].pro);
  25.         int num,st;
  26.         scanf("%d%d",&num,&st);
  27.         for(int i=1;i<=n;i++)
  28.         {
  29.             a[i].lis=num-a[i].lis;
  30.         }
  31.         sort(a+1,a+n+1,comp);
  32.         int ok=1,ans=0;
  33.         a[0].lis=0;
  34.         a[n+1].lis=num,a[n+1].pro=0;
  35.         for(int i=1;i<=n+1;i++)
  36.         {
  37.             if((a[i].lis-a[i-1].lis)<=st)
  38.             {
  39.                 st-=(a[i].lis-a[i-1].lis);
  40.                 v.push(a[i].pro);
  41.             }
  42.             else
  43.             {
  44.                 ans++;
  45.                 if(v.empty())
  46.                 {
  47.                     ok=0;break;
  48.                 }
  49.                 st+=v.top();
  50.                 v.pop();
  51.                 i--;
  52.             }
  53.         }
  54.         if(ok==0)
  55.             ans=-1;
  56.         printf("%d\n",ans);
  57.     }
  58.     return 0;
  59. }
  60. /*
  61. 1
  62. 4 5
  63. 9 5
  64. */

发表评论

表情：
评论列表 （有 0 条评论，49人围观）

还没有评论，来说两句吧...

相关阅读