Thứ Ba, 3 tháng 11, 2020

Cho hai mảng A , B và bài toán liên quan đến tổng và max

Đề bài: $\href{https://codeforces.com/contest/1443/problem/C}{Đây}$

Tóm tắt: Cho hai mảng $a[],b[]$ đều gồm $n$ phần tử (Đánh chỉ số từ 1). Gọi $A=(j_1,j_2,...,j_k)$ và $B=(1,2,...,n)-A$. Tính $S=min(\max\limits_{x\in A}b[x],\sum\limits_{x\in B}a[x])$ với mọi tập chỉ số $A,B$


Lời giải:


+ Bước 0: Sắp xếp $a[]$ theo thứ tự giảm dần


+ Bước 1: Ta sẽ sắp xếp $b[]$ theo thứ tự giảm dần của $a[]$ 


+ Bước 2: Tính prefix-sum của $b[]$ và gọi đó là mảng $c[]$. 


+ Bước 3: Khi đó $S=\min\limits_{i=1}^{n}(max(c[i-1],a[i]))$.


Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define maxn 100005
  5. struct cap{
  6. ll x;
  7. ll y;
  8. };
  9. bool cmp(cap a, cap b){
  10. return a.x>b.x;
  11. }
  12. void solve(){
  13. ll n;
  14. cin>>n;
  15. ll a[n+1],b[n+1];
  16. cap aka[n+1];
  17. ll i;
  18. for(i=1;i<=n;i++) cin>>a[i];
  19. for(i=1;i<=n;i++) cin>>b[i];
  20. for(i=1;i<=n;i++){
  21. aka[i].x=a[i];
  22. aka[i].y=b[i];
  23. }
  24. sort(aka+1,aka+n+1,cmp);
  25. vector<ll> vt;
  26. ll sum=0;
  27. for(i=0;i<n;i++) {vt.push_back(aka[i+1].y); sum+=aka[i+1].y;}
  28. ll c[n+1];
  29. c[0]=0;
  30. partial_sum(vt.begin(),vt.end(),c+1);
  31. ll res=sum;
  32. for(i=1;i<=n;i++){
  33. res=min(res,max(c[i-1],aka[i].x));
  34. }
  35. cout<<res<<'\n';
  36. return ;
  37. }
  38. int main(){
  39. ll t;
  40. cin>>t;
  41. while(t--) solve();
  42. return 0;
  43. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...