P6726 [COCI 2015/2016 #5] POPLAVA 详解

Cells · 2025-07-04 10:17:30 · 题解

思路

像这种有无解情况的题，可以先思考什么时候无解再做有解部分，因为往往无解的思考可以帮助你解题。

思考对于一个 n 的排列，最多能够装多少水。首先可以最大化水平面，也就是将 n 放在最左边，n - 1 放在最右边，这样水平面的高度是 n - 1，然后我们可以按照从左到右的方式放入 1, 2, \dots n - 2，根据等差数列求和可以知道最多放 \frac{(1 + (n - 2)) \times (n - 2)}{2} = \frac{(n - 1) \times (n - 2)}{2} 单位容积的水。所以当 x > \frac{(n - 1) \times (n - 2)}{2} 的时候肯定无解。接下来我们考虑 x 能否取到 [1, \frac{(n - 1) \times (n - 2)}{2}] 中的每一个整数值，如果我们想把最大容积变小 1，那么可以考虑将 n - 2 与 n - 1 交换，这样刚好可以减去 1，就像这样 n, 1, 2, \dots , n - 3, n - 1, n - 2，你可以算一下，刚好少一。我们猜测任何一个数都可以通过刚刚那种交换操作减出来，因为 1, 2, \dots, n - 2 可以拼出来任何一个 [0, \frac{(n - 1) \times (n - 2)}{2} - 1] 中的任何一个数，也就可以满足在区间 [1, \frac{(n - 1) \times (n - 2)}{2}] 中的 x。

Code

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define int LL
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 1e6 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n, x, mxv;

vec<int> num, no;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> x;

    mxv = (n - 1) * (n - 2) / 2;
    if(x > mxv){
        cout << "-1";
        return 0;
    }

    pre(i, n - 2, 1){
        if(x >= i){//如果可以减去这个数 
            num.pb(n - i - 1);//高度和水的容积的转化 
            x -= i;
        }

        else no.pb(n - i - 1);
    }

    cout << n << " ";

    each2(h, num) cout << h << " ";
    cout << n - 1 << " ";
    reverse(all(no));//这个地方是为了保证不用的数从左到右递减，不产生答案 
    each2(h, no) cout << h << " ";

    return 0;
}

再見，再也不見，心碎了飄蕩在海邊，你抬頭就看見…………