poj 2431 Expedition 贪心优先队列

题解

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

然而还是TLE了

TLE代码

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5
 6 using namespace std;
 7
 8 vector<pair<int, int>> dis_fuel(10010);
 9
10 int n;
11 int L, P;
12
13 int ret = 999999;
14
15 void dfs(int idx,int currAddCount)
16 {
17     if (idx == n) {
18         ret = min(ret, currAddCount);
19         return;
20     }
21
22     if (currAddCount >= ret) return;
23
24     if (P + dis_fuel[idx].first >= L) {
25         //当前的油 可以到达 那么选择加油不加油
26
27         P += dis_fuel[idx].second;
28         dfs(idx+1, currAddCount+1);
29
30         P -= dis_fuel[idx].second;
31         dfs(idx + 1, currAddCount);
32     }
33
34     return;
35 }
36
37
38 int solve()
39 {
40     cin >> n;
41
42     for (int i = 0; i < n; i++) {
43         cin >> dis_fuel[i].first >> dis_fuel[i].second;
44     }
45     cin >> L >> P;
46
47     sort(dis_fuel.begin(), dis_fuel.begin() + n, greater<pair<int, int>>());
48
49     dfs(0,0);
50
51     if (ret == 999999) ret = -1;
52     return ret;
53 }
54
55 int main()
56 {
57     cout << solve() << endl;
58
59     return 0;
60 }

TLE!!!

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

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

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5
 6 using namespace std;
 7
 8 vector<pair<int, int>> dis_fuel(10010);
 9
10 int n;
11 int L, P;
12
13
14 int solve()
15 {
16     cin >> n;
17
18     for (int i = 0; i < n; i++) {
19         cin >> dis_fuel[i].first >> dis_fuel[i].second;
20     }
21     cin >> L >> P;
22
23     int ret = 0;
24     sort(dis_fuel.begin(), dis_fuel.begin() + n, greater<pair<int, int>>());
25     priority_queue<int, vector<int>,less<int>> que;
26
27     for (int i = 0; i < dis_fuel.size(); i++) {
28         if (dis_fuel[i].first + P >= L) {
29             que.push(dis_fuel[i].second);
30         }
31         else {
32             while (!que.empty() && dis_fuel[i].first + P < L) {
33                 ret++;
34                 P += que.top();
35                 que.pop();
36             }
37             if (dis_fuel[i].first + P < L) return -1;
38             que.push(dis_fuel[i].second);
39         }
40     }
41
42     if (P < L) return -1;
43     return ret;
44 }
45
46 int main()
47 {
48     cout << solve() << endl;
49
50     return 0;
51 }

View Code

加油

poj 2431 Expedition 贪心 优先队列

poj 2431 Expedition 贪心优先队列