c179 - A.門票
題目描述
題目描述了小 Y 和他的同學去遊樂場，需要購買門票的情況。每個人的門票價格不同，小 Y 有 k 張面額相同的鈔票。題目要求找到最小的鈔票面額，使得小 Y 可以支付所有人的門票費用。售票機的支付方式是按照門票價格從小到大順序支付，如果儲值卡餘額不足，則需要額外投入一張鈔票。
解題思路
本題可以使用二分搜尋法來解決。二分搜尋的範圍是從最大的門票價格到所有門票價格的總和。對於每個可能的鈔票面額，我們可以使用貪心策略來模擬售票機的支付過程。如果能夠成功支付所有門票，則說明該面額是可行的，我們嘗試更小的面額。如果無法支付，則說明該面額太小，我們嘗試更大的面額。
具體來說，judge(v) 函數用於判斷給定面額 v 是否可行。它模擬了售票機的支付過程，如果能夠支付完所有門票，則返回 true，否則返回 false。bs(l, r) 函數使用二分搜尋法來找到最小的可行面額。
複雜度分析
- 時間複雜度: O(N log(Total Sum))，其中 N 是門票數量，Total Sum 是所有門票價格的總和。二分搜尋的範圍是從最大門票價格到總和，每次二分搜尋需要調用
judge函數，judge函數的時間複雜度是 O(N)。 - 空間複雜度: O(1)，除了輸入陣列外，程式使用的額外空間是常數級別。
程式碼
#include <stdio.h>
int n,p[200005],k,ma,total;
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[10],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline bool judge(int v){
if(v<ma)return 0;
int tk=k,tv=v;
for(int i=0;i<n;++i){
if(tv<p[i]){
tv=v;
--tk;
if(tk<=0)return 0;
}
tv-=p[i];
}
return 1;
}
inline int bs(int l,int r){
if(l>r)return l;
int m=(l+r)/2;
if(judge(m))
return bs(l,m-1);
else
return bs(m+1,r);
}
int main() {
n=read();
k=read();
for(int i=0;i<n;++i){
p[i]=read();
if(p[i]>ma)ma=p[i];
total+=p[i];
}
if(n==k)
write(ma);
else
write(bs(ma-1,total+1));
return 0;
}