题解 购物
昨天 N1 的题目质量不错,有意思的期望题。今天又打了打 N1 ,感觉偏套路了(然而我交 WA 了三发)。
看了看大众做法都是 DP ,其实有个简单的 贪心。如果没有这个额外代价,众所周知用一个小根堆把糖果维护起来,每天选代价最小的糖果即可。有一个平方的额外代价看上去就不能贪心了,其实不然,有一个经典套路,把一天的所有糖果按价格排序,然后给第 个糖果的代价加上 即可。
这是因为如果单独考虑在某一天买 个糖果,即使有额外代价,在该天买 个糖果的最优策略仍然是选代价最小的 个,那么该天买糖果的顺序其实是固定的,这样一来不妨直接把额外代价算进糖果本身的代价中。
另外,只要额外代价是凸函数都能这样做,比如 , , 等等。但是 这样的凹函数就不能直接套用了。
参考实现:
#include <cstdio> #include <queue> #include <algorithm> #include <set> #define debug(...) fprintf(stderr, __VA_ARGS__) typedef long long ll; static struct { inline operator int () { int x; return scanf("%d", &x), x; } template<class T> inline void operator () (T &x) { x = *this; } } read; const int maxn = 305; int a[maxn]; std::multiset<int> set; // XXX: 又双叒叕忘了用 multiset !!!! int main () { int n = read, m = read; ll ans = 0; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) read(a[j]); std::sort(a + 1, a + m + 1); for (int j = 1; j <= m; j ++) set.insert(a[j] + j + j - 1); ans += *set.begin(); set.erase(set.begin()); } printf("%lld\n", ans); }