51Nod－1475－建设国家

ACM模版

描述

题解

第一感觉，这道题很像最高的奖励这道题的思路，只是不能用优先队列神马的简单维护。

今天花了些许时间A掉了它，细节繁多，关键是两点，第一：最右端点可以连接两个城市，第二：可以在规定时间内往返首都的城市的选与不选。

针对这两个问题，首先进行排序，将hi从大到小排列，然后开始遍历生成temp_1与temp_2（代码中使用的是temp_0），分别表示两种排放位置。 然后遍历temp_2与temp_1匹配，这里需要说的是，有两种匹配情况，第一是temp_2插入到图中NO和YES位置，第二种情况则是替换到temp_1序列中，而被替换掉的则插入YES位置，然后在这两种情况中取最大的总人口数。

这个题略显刁钻，不好好分析，真的有些难懂……

代码

#include <iostream> #include <algorithm> #include <queue> using namespace std; const int MAXN = 1001; struct city { int hi; int pi; } City[MAXN]; int sum[MAXN]; bool cmp(city a, city b) { return a.hi > b.hi; } int main(int argc, const char * argv[]) { // freopen("/Users/zyj/Desktop/input.txt", "r", stdin); int n; long long H; cin >> n >> H; for (int i = 1; i <= n; i++) { cin >> City[i].hi >> City[i].pi; } sort(City + 1, City + n + 1, cmp); city temp_1[MAXN]; city temp_0[MAXN]; int key_1 = 1; int key_0 = 1; int flag = 0; for (int i = 1; i <= n; i++) { if (key_1 + City[i].hi <= H) { temp_1[key_1++] = City[i]; } else { flag++; int pos = 0; int mink = City[i].pi; for (int j = 1; j + City[i].hi <= H; j++) { if (temp_1[j].pi < mink) { mink = temp_1[j].pi; pos = j; } } if (pos) { temp_0[key_0++] = temp_1[pos]; temp_1[pos] = City[i]; } else { temp_0[key_0++] = City[i]; } } } for (int i = 1; i < key_1; i++) { sum[i] = sum[i - 1] + temp_1[i].pi; } int ans = sum[key_1 - 1]; int key = 0; long long maxh = H - key_1 + 1; for (int i = 1; i < key_1 - 1; i++) { if (temp_1[i].hi <= maxh) { key = i; } } for (int i = 1; i < key_0; i++) { ans = ans > sum[H - temp_0[i].hi] + temp_0[i].pi || H - temp_0[i].hi == 0 ? ans : sum[H - temp_0[i].hi] + temp_0[i].pi; if (key + temp_0[i].hi <= H && key != 0) { ans = ans > sum[key_1 - 1] + temp_0[i].pi ? ans : sum[key_1 - 1] + temp_0[i].pi; } } std::cout << ans << '\n'; return 0; }

参考

51Nod 1163 最高的奖励