思路
考虑贪心策略。
- 当剩下的猫猫数量为偶数的时候,直接取出 \(\large \frac{n}{2}\) 只猫猫即可。
- 否则当剩下的猫猫数量为奇数的时候,则要尽可能保持第二天猫猫的数量为偶数。则要考虑 \(n-\large \frac{n-1}{2}\) 和 \(n-\large \frac{n+1}{2}\) 哪个是偶数。
第二条化简一下就只需要判断 \(\large \frac{n+1}{2}\) 和 \(\large \frac{n-1}{2}\) 哪个是偶数就行了。
AC code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,ans;
signed main(){
cin>>T;
while(T--){
cin>>n;
ans=0;
while(n){
if(n&1){
if(((n-1)>>1)%2==0) n=(n-1)>>1;
else n=(n+1)>>1;
ans++;
}else n>>=1;
}
cout<<ans<<endl;
}
return 0;
}
标签:偶数,frac,猫猫,题解,large,ans,P10892
From: https://www.cnblogs.com/bubble-sort/p/18372728