D - Expedition POJ - 2431——桶排序+贪心+优先队列

╰半夏微凉° 2022-06-18 12:08 226阅读 0赞

Think:  
1题意一个卡车需要到小镇修理，他有一个无限加油箱，耗油量为每单位行程1单位耗油量，路上会经过加油站，假设已小镇作为坐标原点，则给出加油站的一维线性位置和储油量或卡车的初始一维线性位置和初始油量，题意如果能到达小镇，输出到达小镇的经过的最少加油站数量，如果不能到达小镇，则输出-1  
2题目给出了卡车初始位置坐标范围，考虑可以运用桶排序，最少加油站问题则体现了贪心的思想，可以考虑用优先队列记录当前如果油量耗尽时可以加的一次性最大油量  
3题目后台数据猜测：1无重复结点数据 2无加油站位置超过卡车位置的数据

[poj原题链接][poj]

以下为Wrong answer代码  
错误原因：当前符合最优解的加油站重复入队

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    int vid[2000004];
    
    int main()
    {
        int n, i, cnt, flag;
        int u, v, x, y;
    
        priority_queue<int> q;
    
        cnt = 0, flag = 1;
        memset(vid, 0, sizeof(vid));
    
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
            scanf("%d %d", &u, &v);
            vid[u] += v;
        }
        scanf("%d %d", &x, &y);
        while(x != 0)
        {
            if(x <= y)
                break;
    
            for(i = x; i >= x-y && i > 0; i--)
            {
                if(vid[i] != 0)
                    q.push(vid[i]);
            }
    
            x = x-y;
            if(x < 0)
                break;
            else
            {
                if(q.size() == 0)
                {
                    flag = 0;
                    break;
                }
                else
                {
                    y = q.top();
                    q.pop();
                    cnt++;
                }
            }
        }
        if(flag)
            printf("%d\n", cnt);
        else
            printf("-1\n");
        return 0;
    }

以下为Accepted代码

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    int vid[2000004];
    
    int main()
    {
        int n, i, cnt, flag;
        int u, v, x, y;
    
        priority_queue<int> q;
    
        cnt = 0, flag = 1;
        memset(vid, 0, sizeof(vid));
    
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
            scanf("%d %d", &u, &v);
            vid[u] += v;
        }
        scanf("%d %d", &x, &y);
        while(x != 0)
        {
            if(x <= y)
                break;
    
            for(i = x; i >= x-y && i > 0; i--)
            {
                if(vid[i] != 0)
                {
                    q.push(vid[i]);
                    vid[i] = 0;
                }
            }
    
            x = x-y;
            if(x < 0)
                break;
            else
            {
                if(q.size() == 0)
                {
                    flag = 0;
                    break;
                }
                else
                {
                    y = q.top();
                    q.pop();
                    cnt++;
                }
            }
        }
        if(flag)
            printf("%d\n", cnt);
        else
            printf("-1\n");
        return 0;
    }

[poj]: http://poj.org/problem?id=2431