#include<cstdio> using namespace std; int n,f[20001]; int main() { scanf("%d",&n); for(int i=2;i<=n;i++){ if(i&1) f[i]=f[i>>1]+f[(i>>1)+1]; else f[i]=(f[i>>1]<<1); f[i]+=(i>>1); } printf("%d",f[n]); return 0; }
O(nlogn)堆
#include<cstdio> #include<queue> long long n,ans=0; using namespace std; int main() { priority_queue<long long,vector<long long>,greater<long long> > q; scanf("%d",&n); for(int i=1;i<=n;i++)q.push(1); for(int i=1;i<=n-1;i++) { int x=q.top();q.pop(); int y=q.top();q.pop(); ans+=min(x,y); q.push(x+y); } printf("%d",ans); return 0; }