牛客小白月赛30

C 滑板上楼梯

题意

一共有n阶台阶，牛牛一次可以上1或3阶，且不能连续上三阶。
问最少几次能上去。

分析

n的范围是1e12，暴力肯定要超时
要想次数最少，一次就跳尽可能多
但跳一次3阶就需要加上一个1阶，所以一个“周期”是4
每连续两次最多上4阶

但是一共只有n阶台阶，不能跳多了
如果台阶数n正好是4的倍数，那么最少需要(n/4)个周期，即跳(n/4)*2次

但如果n比4的倍数小1，那么最后一个周期跳过3阶后就不需要再跳1阶了，只有最后一个周期不全
需要(n+1)/4个周期，其中(n+1)/4-1个周期跳了两次，最后一个周期跳了1次，即跳了2*((n+1)/4-1)+1次

如果n比4的倍数小2或3（也就是比4的倍数大1或2），那么只能跳(n+1)/4向下取整个整周期，再一次1阶跳上剩下的楼梯，即为2(n+1)/4+(n-(n+1)/44)次

AC代码

#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define fi(i,l,r) for(int i=l;i<r;i++) 
#define cd(a) scanf("%d",&a)
#define ll long long
//不要再爆long long了！！！！！！！！不要再爆long long了！！！！！！！ 

int main()
{
    ll n;
    cin>>n;
    ll k=(n+1)/4;
    ll ans=0;
    ans=2*k;
    ans+=n-k*4;
    printf("%lld\n",ans);
    return 0;
}