題意：
? ? ?給你n個任務(wù)，每個任務(wù)有兩個權(quán)值，t[i],b[i]，前面的是完成任務(wù)所需時間，后面的那個是個參數(shù)，每個任務(wù)完成的代價是完成當前任務(wù)總時間（之前的+現(xiàn)在的）
sumt * b[i],問你完成所有任務(wù)的總花費最小是多少。
思路：
? ? ?水貪心吧，不給證明了，沒啥意思，就想象一下，那個東西價值貴就先干那個就行了

價值等于 b[i] / t[i],價值貴的放到最后干會吃虧的。

#include<stdio.h> #include<algorithm> using namespace std;typedef struct {__int64 x ,y;double key; }NODE;bool camp(NODE a ,NODE b) {return a.key > b.key; }NODE node[110000];int main () {int n ,i;while(~scanf("%d" ,&n)){for(i = 1 ;i <= n ;i ++)scanf("%I64d" ,&node[i].x);for(i = 1 ;i <= n ;i ++){scanf("%I64d" ,&node[i].y);node[i].key = node[i].y * 1.0 / node[i].x;}sort(node + 1 ,node + n + 1 ,camp);__int64 sum = 0 ,ans = 0;for(i = 1 ;i <= n ;i ++){sum += node[i].x;ans += sum * node[i].y;}printf("%I64d\n" ,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4882 水贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。