C 上楼梯 中国石油大学新生训练赛#11

输出

样例输入 提交状态

思路：

看表易分析规律 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4

看数据范围发现10^19 考虑写一个时间复杂度为O(1)的答案

如果n = 5, m = 5 那么是1 1 1 1 1（每次走一步，总共耗5体力）

如果m成为6，那么就是1 1 1 2 

不难发现数对{1, 1} -> {2} 需要多花1点体力

同理 {1, 2} -> {3} 需要多花2点体力 可以推出所有的压缩方式 压缩对象的数值越大 多花费的体力越多

也就是说所需的代价越高，在这个思想下，不难发现，最佳答案是优先将所有1化为2 直到不能化了 再将2化为3

由于需要O(1)的答案，所以直接写数和判断就行了~

    ll T1= n;
    ll T2= (n - (n % 2)) * 3 / 2 + n % 2;
    ll T3= (n - (n % 3)) * 2 + n % 3;
    ll T4= (n - (n % 4)) * 5 / 2 + n % 4;

T2是尽力将所有走法的全部都变成2所需的体力，最后加上n % 2便是剩下的"1"

T3，T4同理，只不过状态中余的数依然是“1”，所以在代码中需要特判

例如n % 3 = 1 则最后会剩下个1 后面压缩的时候就需要优先压缩{1, 3} -> {4} 

然后再压缩{3, 3, 3, 3} -> {4, 4, 4} (也就是lcm的两个因子之间的转移) 

题解：

/*
************************************
***********emu^w^***********
 
*/

#include 
using namespace std;
#define x first
#define y second
const int P = 13131;
#define ll long long
const int mod = 1E6 + 7;
const int INF = 0x3f, sINF = 0x3f3f3f3f;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
//
const int N = 500010;
ll n, m;

int main()
{
    cin>>n>>m;

    ll T1= n;
    ll temp = m;
    ll T2= (n - (n % 2)) * 3 / 2 + n % 2;
    ll T3= (n - (n % 3)) * 2 + n % 3;
    ll T4= (n - (n % 4)) * 5 / 2 + n % 4;
//    cout<
    
    if(m >= T1 && m < T2) {
        temp -= n;
        cout<endl;
    }  
    else if(m >= T2 && m < T3)
    {
        temp -= T2;
        ll ans = n / 2 + n % 2;
        if(n % 2) if(temp >= 2) {
            temp -= 2;
            ans--;
        }
        if(temp >= 3) ans -= temp / 3;
        cout<endl;
    }
    else if(m >= T3 && m < T4) {
        temp -= T3;
        ll ans = n / 3 + n % 3;
        if(n % 3 == 2) {
            temp--;
            ans--;
        }
        if(n % 3 == 1 && temp >= 3)  {
            temp -= 3;
            ans--;
        }
        if(n % 3 == 2 && temp >= 5) {
            temp -= 5;
            ans--;
        }
        if(temp >= 6) ans -= temp / 6;
        
        cout<endl;
    }
    else {
        ll ans = n / 4 + n % 4;
        temp -= T4;
        if(n % 4 == 2 && temp >= 1) {
            temp--;
            ans--;
        } 
        if(n % 4 == 3 && temp >= 1) {
            temp--;
            ans--;
        }
        if(n % 4 == 3 && temp >= 2) 
        {
            temp -= 2;
            ans--;
        }
        cout<endl;
    }


}

时间复杂度: O(1);

类型： 条件判断