Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define maxn 100005
- struct cap{
- ll x;
- ll y;
- };
- bool cmp(cap a, cap b){
- return a.x>b.x;
- }
- void solve(){
- ll n;
- cin>>n;
- ll a[n+1],b[n+1];
- cap aka[n+1];
- ll i;
- for(i=1;i<=n;i++) cin>>a[i];
- for(i=1;i<=n;i++) cin>>b[i];
- for(i=1;i<=n;i++){
- aka[i].x=a[i];
- aka[i].y=b[i];
- }
- sort(aka+1,aka+n+1,cmp);
- vector<ll> vt;
- ll sum=0;
- for(i=0;i<n;i++) {vt.push_back(aka[i+1].y); sum+=aka[i+1].y;}
- ll c[n+1];
- c[0]=0;
- partial_sum(vt.begin(),vt.end(),c+1);
- ll res=sum;
- for(i=1;i<=n;i++){
- res=min(res,max(c[i-1],aka[i].x));
- }
- cout<<res<<'\n';
- return ;
- }
- int main(){
- ll t;
- cin>>t;
- while(t--) solve();
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét