题解 购物

昨天 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);
}
全部评论
Orzzz%%%%%%
点赞 回复 分享
发布于 2022-07-15 10:35

相关推荐

11-09 14:54
已编辑
华南农业大学 产品经理
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
10-06 12:46
门头沟学院 Java
跨考小白:定时任务启动
点赞 评论 收藏
分享
8 1 评论
分享
牛客网
牛客企业服务