首页 > 代码库 > hdoj 4882 ZCC Loves Codefires 【贪心】
hdoj 4882 ZCC Loves Codefires 【贪心】
题目大意:求最少被扣除的时间
策略 如题;
对于两个邻近的题目i, j,对于他们对于在他们之前解决的题目的总时间的贡献t是不影响的,对于他们之后的总时间也不影响
这就推得对每一对相邻的他们对前后都是无影响的, 如果是交换的话原来是(t+e[i])*k[i] + (t+e[i]+e[j])*k[j], 就变成了(t+e[j])*k[j] + (t+e[i]+e[j])*k[i]
改变的就是 原来的 e[i]*k[j] 变成了 e[j]*k[i] 这两个式子之间满足 e[i]*k[j] < e[j]*k[i] => e[i]/k[i] < e[j]/k[j],
故我们只需要算出e与k的商 在从小到大排序,即满足最优解.
易错点:因为题目给出的数据过大,要用__int64 来计算 , re了三次,数组开小了
AC by SWS
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4882
代码:
#include<stdio.h>#include<algorithm>using namespace std;typedef struct{ int k, e; double r;}str;str s[100100]; //这里int cmp(str a, str b){ if(a.r < b.r) return true; return false;}int main(){ int n, i, j; while(scanf("%d", &n) == 1){ for(i = 0; i < n; i ++) scanf("%d", &s[i].e); for(i = 0; i < n; i ++) scanf("%d", &s[i].k), s[i].r = (s[i].e+0.0)/s[i].k; sort(s, s+n, cmp); __int64 sum = 0, t = 0; for(i = 0; i < n; i ++){ t += s[i].e; sum += t*s[i].k; } printf("%I64d\n", sum); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。