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

思路

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

思考对于一个

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;
}

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

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

文章操作

思路

Code

相关推荐

评论

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