AT4517 [AGC032B] Balanced Neighbors

_xbn · 2021-06-11 09:49:16 · 题解

分 n 的奇偶性讨论。

当 n 为偶数时，我们可以把 (1,n)，(2,n-1) 等配对这样的构造是合法的。

当 n 为奇数时，我们可以把 n 单独分为一组，其余按照偶数配对处理，这样是肯定合法的。

#include <bits/stdc++.h>
using namespace std;
int n, m, k, p, q, ans, sum;
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-') f=-1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x=(x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    n = read();
    int flag = n % 2 ? n: n + 1;
    for(int i = 1; i < n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if(i + j == flag)continue;
            m++;
        }
    }
    cout << m << endl;
    for(int i = 1; i < n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if(i + j == flag)continue;
            cout << i << " " << j << endl;
        }
    }
    return 0;
}