挑战程序设计竞赛 (优先队列) POJ 2431 3253

POJ 2431 Expedition

点击这里 查看题目

真的自闭，一个晚上写一道题。就是不知道哪里WA了，最后发现题目没有说一定是顺序输入的加油站(stop)，所以在具体实现的时候需要先sort一下。/微笑

出错点

1. The first integer is the distance from the town to the stop; 2至N+1行给出的第一个数值是距终点(town)的距离。
2. 题目并没有说加油站(stop)是按照顺序给出，所以需要sort
3. 没有将终点考虑进去（终点是否可达）

针对出错点3的样例：

INPUT:
4
14 4
15 2
21 5
25 10
35 10OUTPUT:
-1

解题思路

从挑战程序设计竞赛来的，所以思路就是按照书上写的。不过我这里的while循环简单一些，因为走1单位丢1单位的油，所以不需要像书里那样考虑油桶还省多少油。每次把所有的加油站push到优先队列中，当遇到到达不了的加油站，就pop优先队列即可，直到到达终点(town)。

代码

尽量还原及优化挑战程序设计竞赛的代码。

重点代码

bool solve(){priority_queue<int> q;int pos =  P;for(int i = 0; i <= N; i++){while(pos < s[i].dis){if(q.empty()){cout << "-1" << endl; return false;}pos += q.top();q.pop();ans++;}q.push(s[i].fuel);}return true; 
}

其他部分

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 10000
using namespace std;struct node{int dis, fuel;
};
node s[MAX+5];
int N, L, P, ans = 0;bool cmp(node x, node y){return x.dis < y.dis ? 1:0;
}int main(){cin >> N;for(int i = 0; i < N; i++){cin >> s[i].dis;cin >> s[i].fuel;}cin >> L >> P; //错误点1for(int i = 0; i < N; i++)s[i].dis = L-s[i].dis;//没有下面两行就是没有考虑到错误点3s[N].dis = L;s[N].fuel = 0;//错误点2sort(s, s+N+1, cmp);if(solve()) cout << ans << endl;return 0;
} 

POJ 3253 Fence Repair

点击这里 查看题目

解题思路

这题没有什么解题思路，能想到用优先队列解题就很简单了，而且并没有要求输入多组数据。

代码

#include <iostream>
#include <queue>
#define MAX_N 20000
typedef long long ll;
using namespace std;
int N, L[MAX_N+5];void solve(){ll ans = 0;priority_queue<ll, vector<ll>, greater<ll> > q;for(int i = 0; i < N; i++)q.push(L[i]);while(q.size() > 1){ll min1 = 0, min2 = 0;min1 = q.top(), q.pop();min2 = q.top(), q.pop();ans += min1 + min2;q.push(min1+min2);}cout << ans << endl;
}int main(){cin >> N;for(int i = 0; i < N; i++)cin >> L[i];solve();return 0;
}