首页 > 代码库 > HDU 4882 ZCC Loves Codefires(贪心水)
HDU 4882 ZCC Loves Codefires(贪心水)
HDU 4882 ZCC Loves Codefires
题目链接
题意:给定一些任务,每个任务有e,k,e表示完成需要时间,k表示完成后消耗,为完成时间t * k,求一个顺序使得完成消耗最少
思路:贪心,知道k大的尽量早晚餐,t小的尽量早完成,所以t / k小的尽量早完成,排个序即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100005; int n; struct Q { __int64 e, k; } q[N]; bool cmp(Q a, Q b) { return a.e * b.k < a.k * b.e; } int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) scanf("%I64d", &q[i].e); for (int i = 0; i < n; i++) scanf("%I64d", &q[i].k); sort(q, q + n, cmp); long long ans = 0, now = 0; for (int i = 0; i < n; i++) { now += q[i].e; ans += now * q[i].k; } printf("%I64d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。