Posted on 2007-10-17 17:25
ZelluX 閱讀(969)
評(píng)論(5) 編輯 收藏 所屬分類:
Algorithm
我的做法是枚舉最遠(yuǎn)到達(dá)的湖，減去相應(yīng)的時(shí)間后貪心。
貪心時(shí)需要建立一個(gè)堆，用了STL中的priority_queue，然后就不知道如何設(shè)置less<>方法了。。。
最后是通過自定義一個(gè)類node解決的
一開始寫的operator<方法邏輯上有問題，VS 2005跑了一會(huì)兒就冒出個(gè) Debug assert error，這個(gè)挺贊的
導(dǎo)致我WA的幾個(gè)數(shù)據(jù)：
1) 收益為0的幾組數(shù)據(jù)。由于一開始設(shè)置的max值為0，因此當(dāng)正解也是0時(shí)并沒有記錄下當(dāng)前的最優(yōu)解。max初始為負(fù)值即可。
2) 同樣是0導(dǎo)致的問題。0收益的釣魚點(diǎn)也可能出現(xiàn)在堆中，此時(shí)應(yīng)該放棄這個(gè)點(diǎn)，把時(shí)間保留給序數(shù)大的釣魚點(diǎn)。
另外我有這次比賽的測(cè)試數(shù)據(jù)和標(biāo)程，需要的朋友留言即可。
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
class node 
{
public:
int first, second;
node(int x, int y)
{
first = x;
second = y;
}
bool operator< (const node &rhs) const
{
if (second < rhs.second)
return true;
else if (second > rhs.second)
return false;
else return (first > rhs.first);
}
};
int main()
{
int n, h;
int d[26], t[26], f[26];
priority_queue<node, vector<node>, less<vector<node>::value_type> > heap;
vector<int> best(26);
cin >> n;
while (true) {
if (n == 0) break;
cin >> h;
for (int i = 1; i <= n; i++)
cin >> f[i];
for (int i = 1; i <= n; i++)
cin >> d[i];
t[0] = 0;
for (int i = 1; i < n; i++)
cin >> t[i];
best.clear();
int max = -1;
// i indicates the last lake
for (int i = 1; i <= n; i++) {
vector<int> tempBest(26);
int valueGet = 0;
int timeLeft = h * 12;
for (int j = 1; j <= i; j++)
timeLeft -= t[j - 1];
if (timeLeft <= 0) break;
while (!heap.empty())
heap.pop();
for (int j = 1; j <= i; j++)
heap.push(node(j, f[j]));
while ((!heap.empty()) && (timeLeft > 0)) {
int next = heap.top().first;
if (heap.top().second > 0) {
timeLeft--;
tempBest[next]++;
valueGet += heap.top().second;
}
int valueLeft = heap.top().second - d[next];
heap.pop();
if (valueLeft > 0)
heap.push(node(next, valueLeft));
}
if (valueGet > max) {
max = valueGet;
best = tempBest;
if (timeLeft > 0)
best[1] += timeLeft;
}
}
printf("%d", best[1] * 5);
for (int i = 2; i <= n; i++)
printf(", %d", best[i] * 5);
printf("\nNumber of fish expected: %d\n", max);
cin >> n;
if (n != 0) cout << endl;
}
return 0;
}