HDU 4882 ZCC Loves Codefires

题目链接

题意：给定一些任务，每个任务有e，k，e表示完成需要时间，k表示完成后消耗，为完成时间t * k，求一个顺序使得完成消耗最少

思路：贪心，知道k大的尽量早晚餐，t小的尽量早完成，所以t / k小的尽量早完成，排个序即可

代码：

#include 
  
   
#include 
   
     #include 
    
      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; }