ccbeginner

ZJ c471

Oct 13th, 2020
42
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Judge: https://zerojudge.tw/ShowProblem?problemid=c471
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. // This problem is a little harder than previous problems.
  7. // The idea is about greedy.
  8. // Let us consider situation when there're only two stuff: stuff A and B
  9. // If A stack on B, it costs f(A) * w(B), otherwise it costs f(B) * w(A).
  10. // Formally, if (f(A) * w(B) < f(B) * w(A)), we should let A stack on B to minimize the cost, and vice versa.
  11. //
  12. // Now we can extend to N stuff and sort them, and than calculate the answer!
  13.  
  14. struct stuff{
  15.     int w,f; //w => weight, f => times to take
  16. };
  17. stuff stuffs[100000];
  18.  
  19. // compare function, for sorting usage
  20. bool cmp(stuff a, stuff b){
  21.     return a.w*b.f < b.w*a.f;
  22. }
  23.  
  24. int main(){
  25.     // inputs
  26.     int n;
  27.     cin >> n;
  28.     for(int i = 0; i < n; ++i){
  29.         cin >> stuffs[i].w;
  30.     }
  31.     for(int i = 0; i < n; ++i){
  32.         cin >> stuffs[i].f;
  33.     }
  34.     // sort method, see more details https://officeguide.cc/cpp-sort-function-tutorial-examples/
  35.     sort(stuffs, stuffs + n, cmp);
  36.     // declare the answer and the sum of weight
  37.     // remember to use long long int to prevent from integer overflow
  38.     long long int ans = 0, sum = 0;
  39.     for(int i = 0; i < n; ++i){
  40.         // calculation
  41.         ans += sum * stuffs[i].f;
  42.         sum += stuffs[i].w;
  43.     }
  44.     cout << ans << '\n';
  45.     return 0;
  46. }
RAW Paste Data