本文主要是介绍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);
}
}
这篇关于hdoj 4882 ZCC Loves Codefires 【贪心】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
