题解：P15266 「UTOI 1A」sp! dusttale

ingo_dtw · 2026-02-11 19:06:14 · 题解

首先不难注意到，一个长度为 n 的排列最多有 n-2 个峰或谷。而如果我们想要 \displaystyle \max^{n}_{i=1}(p_i+q_i) 最小，那么最优的情况就是所有的 p_i+q_i=n+1 也就是两两配对，而想要达成这种情况，比如 p 有 x 个峰 y 个谷，那么与它相匹配的 q 就有 y 个峰 x 个谷。

所以，答案不是 n+1 就是 -1，那么什么情况下才是 -1 呢？首先，当 n\le 2 时，一定是 -1 因为此时形成不了峰或谷，当 \frac{n-2}{2}<m 时，也是 -1，因为形成不了 m 个峰和谷。

:::success[Ac Code]

#include <bits/stdc++.h>
using namespace std;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
#define int long long
#define rint register int
#define R register
#define _ read<int>()
template<class T>inline T read()
{
    R T r=0,f=1;R char c=gc();
    while(!isdigit(c))
    {
        if(c=='-') f=-1;
        c=gc();
    }
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=gc();
    return f*r;
}
inline void out(rint x)
{
    if(x<0) pc('-'),x=-x;
    if(x<10) pc(x+'0');
    else out(x/10),pc(x%10+'0');
}

signed main()
{       
    rint t=_;
    while(t--)
    {
        rint n=_,m=_;
        if(((n-2)>>1)<m||n<=2) puts("-1");
        else 
        {
            out(n+1);pc('\n');
        }
    }
    return 0;
}//我也要写吗

:::