题解：SP26348 NINJA5 - K NUMBERS

lixiangyu123456789 · 2026-10-21 15:41:55 · 题解

题目大意

从 1 到 N 中选出最多的整数，且被选的两个数之间互不相邻，再给定 K 个数必选。

思路：

先将题目给定的 K 个数排序，因为不能选相邻的，所以区间的两边不能选，最好的办法即为隔一个取一个，最左侧可以取 \lfloor \frac{a_1-1}{2} \rfloor 个数。中间相邻两个可以取 \lfloor \frac{a_{i+1}-a_i-2}{2} \rfloor 个数，最右侧可以取 \lfloor \frac{n-a_k}{2} \rfloor 个数。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[2101010];
int main()
{
    int t,n,k;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int u=0;
        cin>>n>>k;
        for(int j=1;j<=k;j++)
        {
            cin>>a[j];
        }
        sort(a+1,a+k+1);
        for(int j=1;j<=k;j++)
        {
            if(j==1)
            {
                u+=(a[1]-1)/2;
            }
            else
            {
                u+=(a[j]-a[j-1])/2-1;
            }
            cout<<u<<endl;
        }
        u+=(n-a[k])/2;
    }
    return 0;
}