poj 2431 Expedition 贪心 优先队列 题解《挑战程序设计竞赛》

地址 http://poj.org/problem?id=2431

    

 

题解

朴素想法就是dfs 经过该点的时候决定是否加油 中间加了一点剪枝 如果加油次数已经比已知最少的加油次数要大或者等于了 那么就剪枝

然而 还是TLE了

TLE代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int>> dis_fuel(10010);

int n;
int L, P;

int ret = 999999;

void dfs(int idx,int currAddCount)
{
    if (idx == n) {
        ret = min(ret, currAddCount);
        return;
    }

    if (currAddCount >= ret) return;

    if (P + dis_fuel[idx].first >= L) {
        //当前的油 可以到达 那么选择加油不加油

        P += dis_fuel[idx].second;
        dfs(idx+1, currAddCount+1);

        P -= dis_fuel[idx].second;
        dfs(idx + 1, currAddCount);
    }

    return;
}


int solve()
{
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> dis_fuel[i].first >> dis_fuel[i].second;
    }
    cin >> L >> P;

    sort(dis_fuel.begin(), dis_fuel.begin() + n, greater<pair<int, int>>());
    
    dfs(0,0);

    if (ret == 999999) ret = -1;
    return ret;
}

int main()
{
    cout << solve() << endl;

    return 0;
}

考虑下经过一个加油站就是增加了一个加油的机会 那么我们尝试不加油继续往前走 走到没有了 看看能经过多少加油站 然后从里面选择加油最多的那个机会 加油 再继续前行

这是很显然的贪心策略 既然要加油次数最少 那么在能加油的机会里贪心选择即可.未细加证明 但是AC了 说明思路是正确的

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int>> dis_fuel(10010);

int n;
int L, P;


int solve()
{
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> dis_fuel[i].first >> dis_fuel[i].second;
    }
    cin >> L >> P;

    int ret = 0;
    sort(dis_fuel.begin(), dis_fuel.begin() + n, greater<pair<int, int>>());
    priority_queue<int, vector<int>,less<int>> que;

    for (int i = 0; i < dis_fuel.size(); i++) {
        if (dis_fuel[i].first + P >= L) {
            que.push(dis_fuel[i].second);
        }
        else {
            while (!que.empty() && dis_fuel[i].first + P < L) {
                ret++;
                P += que.top();
                que.pop();
            }
            if (dis_fuel[i].first + P < L) return -1;
            que.push(dis_fuel[i].second);
        }
    }

    if (P < L) return -1;
    return ret;
}

int main()
{
    cout << solve() << endl;

    return 0;
}