天津网站建设包括哪些,上海网站建设排名公司哪家好,智库网站建设方案,微盟企业微信助手正题
题目链接:https://www.luogu.com.cn/problem/CF891B 题目大意
给出nnn个数字互不相同的一个序列aaa#xff0c;求它的一个排列bbb#xff0c;使得选出任意一个1∼n1\sim n1∼n的下标真子集#xff0c;都有aaa的对应下标和不等于bbb的对应下标和。 1≤n≤22,0≤ai≤10…正题
题目链接:https://www.luogu.com.cn/problem/CF891B 题目大意
给出nnn个数字互不相同的一个序列aaa求它的一个排列bbb使得选出任意一个1∼n1\sim n1∼n的下标真子集都有aaa的对应下标和不等于bbb的对应下标和。
1≤n≤22,0≤ai≤1091\leq n\leq 22,0\leq a_i\leq 10^91≤n≤22,0≤ai≤109 解题思路
首先考虑对于每个aia_iai向它对应bib_ibi连边然后如果连出来的不是一个大小为nnn的环的话显然是错的因为一次选择相当于选择环上的一条边那么选一个环显然是对的。
然后现在问题就变成了找一个环排列满足以上的条件再考虑怎么找这个环排列发现对应环上选择的连续一段那么最后肯定是头而且尾−-−然后中间的不计贡献换句话就是无法在这个环上选出一个子序列然后/−/-/−交错使得和为000。
对于这个问题的构造就很简单了直接选择一个递增的序列这样每个肯定有个比他更大/小的−-−与它抵消。
不过这样看上去其实是想复杂了换种想法其实就是对于每个选出的除了最大的aia_iai都有一个更大的bib_ibi对应然后如果选择了最大的aia_iai那么这个差值需要选择另外n−1n-1n−1个才能抵上。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N30;
int n,a[N],b[N];
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]),b[i]a[i];sort(b1,b1n);for(int i1;in;i){if(a[i]b[n])printf(%d ,b[1]);else printf(%d ,b[upper_bound(b1,b1n,a[i])-b]);}return 0;
}
