题解：P14054 [SDCPC 2019] Sekiro

TCY1234567 · 2025-09-18 11:57:29 · 题解

题意

现在有两个数 n 和 k，现在你要执行 k 次操作，每一次将 n 变成 \lceil n/2 \rceil，问你最后的 n 是多大

题解

首先 k 非常大，直接模拟肯定不行，但我们发现，当 n = 10^9 时也最多只会除 30 次后就在 1 徘徊。所以当 k \ge 30 时，直接输出 1 即可。否则直接模拟，发现时间复杂度一定是正确的。

正确代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        if(n==0)
        {
            puts("0");
            continue;
        }
        if(k>=30) puts("1");
        else
        {
            while(k!=0)
            {
                n = n/2+n%2;
                k--;
            }
            printf("%d\n",n);
        }
    }
}