P17761

br_liu · 2026-10-24 14:12:16 · 题解

思路

题意比较好理解，我就不加以解释了。下文以蓝色格子表示种子，红色格子表示西瓜。

注意到当种子足够多的情况下，长出西瓜的格子数量就是 2n-k。那么什么时候西瓜和西瓜种子可以遍布田地呢？

注意到种子的种植只有可能是两种情况，即 和 。

那么如果想铺满田地，必须用第一种情况铺两边，第二种情况铺中间。即 。可以看出，从第一列开始每两列要放一个种子才能使得种子和西瓜铺满田地。也就是说，ans=2n-k(2k>n)。

那么如果铺不满的话，我们应该尽量使第二种情况更多，也就是应该先铺中间，再铺两边。而可以看出来，第二种种子可能的数量是 k_2=\lceil\frac{n}{2}-2\rceil。那么，ans=3k(k\le\lceil\frac{n}{2}-2\rceil)。

注意到如果 n 是奇数的话，那么所有情况就都已经就都已经讨论完了。但是如果 n 是偶数，那么就还有一种情况，即 \frac{n}{2}<k\le\lceil\frac{n}{2}-2\rceil，也就是 k=\frac{n}{2} 的情况。不难看出，这时候 ans=3k-1。

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        if(2*k>n)cout<<2*n-k<<'\n';
        else if(n%2==0&&k==n/2)cout<<3*k-1<<'\n';
        else cout<<3*k<<'\n';
    }
}

AC 记录

如果有任何疑问可以私信我，我会尽其所能地解答。