b936 - Kevin 愛橘子
題目描述
題目描述了 Kevin 擁有一顆包含 N 片橘子的橘子，他希望將橘子分給盡可能多的人，且每個人至少能吃到 M 片橘子。Kevin 每次可以將橘子分成兩半，如果橘子片數為偶數，則分成 N/2 和 N/2；如果橘子片數為奇數，則分成 (N-1)/2 和 (N+1)/2。題目要求計算最多可以分給多少人。
解題思路
這道題的核心在於觀察橘子分法的規律。當 N 很大時，直接模擬分法會超時。觀察可以發現，分法實際上是一種二元樹的結構。Allot(n) 函數遞迴地計算可以分給多少人。
- 如果
n < m，則無法分給任何人，返回 0。 - 如果
n < 2m，則只能分給 1 個人。 - 如果
n < 3m - 1，則只能分給 2 個人。 - 如果
n是奇數，則分法取決於(n >> 1) & 1的值，分別遞迴計算Allot(n >> 2) + 3 * Allot((n >> 2) + 1)和3 * Allot(n >> 2) + Allot((n >> 2) + 1)。 - 如果
n是偶數，則直接返回Allot(n >> 1) << 1。
這個遞迴關係式反映了橘子分法的不同情況，通過遞迴計算，可以有效地找到最多可以分給多少人。
複雜度分析
- 時間複雜度: O(log(N))。 每次遞迴調用都會將問題規模減小到原來的 1/2 或接近 1/2，因此時間複雜度是對數級別。
- 空間複雜度: O(log(N))。 遞迴調用的深度決定了空間複雜度，最壞情況下遞迴深度為 log(N)。
程式碼
#include<bits/stdc++.h>
using namespace std;
long long n,m;
inline long long read(){
long long a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(long long x) {
if(x==0)
putchar_unlocked('0');
else{
long long stk[18],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
long long Allot(long long now) {
if (now < m)
return 0;
if (now < (m << 1))
return 1;
if (now < (m << 2) - 1)
return 2;
if (now & 1) {
if ((now >> 1) & 1)
return Allot(now >> 2) + 3 * Allot((now >> 2) + 1);
return 3 * Allot(now >> 2) + Allot((now >> 2) + 1);
}
return Allot(now >> 1) << 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
while(n=read()){
m=read();
if(n<m)puts("0");
else write(Allot(n)),puts("");
}
}