Codeforce 1539D-PriceFixed
題目連結: https://codeforces.com/problemset/problem/1539/D
題目大意:
一間商店裡,有$n$種商品,Lena 想買各$a_i$個,一次買一個,每個商品都是$2$元。
如果你在買第$i$種商品之前已經買了$b_i$個商品,那麼該商品只需花費$1$元。
請問: Lena最少需花多少錢才能買齊。
Sample
$Sample$ $Input$
3
3 4
1 3
1 5
$Sample$ $Output$
8
8
$Sample$ $Input$
5
2 7
2 8
1 2
2 4
1 8
$Sample$ $Output$
12
Solution
考慮兩種商品 $X,Y$,且有$b_X<b_Y$,如果我們想要買到優惠,顯然我們比較容易達到 $X$ 的量(即 $b_X$ ),所以我們可以將每種商品 $i$ 先依 $b_i$ 排序,接著利用雙指針,假設現在已經買了 $tot$ 個商品,而商品 $i$ 需要 $b_i-tot$ 個才能有優惠,那麼我們就從後面買 $b_i-tot$個商品,重複執行直到全部買完。
Code
#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>
#define fi first
#define se second
#define SpeedUP ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n;
pi a[100005];
// first 表 要買的個數(a) second 表 優惠需求的量(b)
void sol(){
cin >>n;
for (int i=0;i<n;i++) cin >>a[i].fi>>a[i].se;
sort(a,a+n,[](pi lh,pi rh){
return lh.se<rh.se; // 依照 b_i 排序
});
int r=n-1,tot=0,ans=0;
for (int i=0;i<n;i++){
if (i==r) break; // 當 i=r 時,直接跳出 之後處理
if (tot>=a[i].se){
ans+=a[i].fi;
tot+=a[i].fi;
a[i].fi=0;
}
else{
while (r>i&&a[i].se-tot-a[r].fi>=0){
tot+=a[r].fi;
ans+=2*a[r].fi;
r--;
}
if (i==r) break;
int k=a[i].se-tot;
ans+=2*k;
a[r].fi-=k;
tot+=k;
ans+=a[i].fi;
tot+=a[i].fi;
}
}
// 處理 i==r 時
if (tot>=a[r].se) {
cout <<ans+a[r].fi;
}
else if (tot<a[r].se&&tot+a[r].fi>=a[r].se){
cout <<ans+(a[r].se-tot)*2+(a[r].fi-(a[r].se-tot));
}
else{
cout <<ans+a[r].fi*2;
}
}
signed main(){
SpeedUP
int tEst=1;
//cin >>tEst;
while (tEst--) sol();
return 0;
}
時間複雜度: $O(nlogn+n)$,排序+計算。
這題想法不難,可是我實作太弱qwq,卡了很久才找到bug,AC code也很醜。