Codeforces 892 D.Gluttony
2 seconds
256 megabytes
standard input
standard output
You are given an array a with n distinct integers. Construct an array b by permuting a such that for every non-empty subset of indices S = {x1, x2, ..., xk} (1 ≤ xi ≤ n, 0 < k < n) the sums of elements on that positions in a and b are different, i. e.
The first line contains one integer n (1 ≤ n ≤ 22) — the size of the array.
The second line contains n space-separated distinct integers a1, a2, ..., an (0 ≤ ai ≤ 109) — the elements of the array.
If there is no such array b, print -1.
Otherwise in the only line print n space-separated integers b1, b2, ..., bn. Note that b must be a permutation of a.
If there are multiple answers, print any of them.
2
1 2
2 1
4
1000 100 10 1
100 1 1000 10
An array x is a permutation of y, if we can shuffle elements of y such that it will coincide with x.
Note that the empty subset and the subset containing all indices are not counted.
题目大意:给定一个数组a,将a中的元素调换位置变成b数组,使得对于每一个下标子集,a中对应下标的元素和不等于b中对应下标的元素和.
分析:构造题.如果第i位的数是第j大的,那么就把第j+1大的放在第i位,如果已经是最大的了,就把最小的放在第i位,这样一定是对的.证明的话就是看是否选最大的那个数.
这个数据范围真的是让人分分钟想到状压......
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n, a[]; struct node
{
int x, id;
}e[]; bool cmp(node a, node b)
{
return a.x < b.x;
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%d", &e[i].x);
e[i].id = i;
}
sort(e + , e + + n, cmp);
for (int i = ; i <= n; i++)
a[e[i].id] = i;
for (int i = ; i <= n; i++)
{
int t = (a[i] + ) % n;
if (t == )
t = n;
printf("%d ", e[t].x);
} return ;
}
最新文章
- Feathers UI 性能优化
- check fasta format
- 基础知识系列☞各版本下IIS请求处理过程区别
- Document.getElementById 与 $(&#39;#id&#39;)的区别
- css的transition 属性
- ASP.NET实现在线人员实时显示
- localtime和localtime_r
- Java中,&;&;与&;;||与|的区别
- C++对象模型笔记之程序设计模型
- 移动web页面支持弹性滚动的3个方案
- A*寻路算法入门(一)
- Boost 序列化
- Easyui datagrid 绑定本地Json数据
- 典型 python 小练习
- Deformable Convolutional Networks-v1-v2(可变形卷积网络)
- 【java】浅析java组件中的布局管理器
- 10 python os&;sys 模块
- 去除html代码中的标签
- sqlserver 若字段定义的类型为datetime
- oracle 11g physical standby switchover
热门文章
- Java GC基础
- 应用-如何使不同的企业使用独自的数据源。使用ejb3.0+jboss6.2EAP+JPA
- UVA 1479 Graph and Queries (Treap)
- 洛谷 P2604 [ZJOI2010]网络扩容
- (转)Spring的bean管理(注解方式)
- gitee 如何创建仓库 及发布
- CodeForces - 930A Peculiar apple-tree(dfs搜索)
- webpack之source map
- 不同子系统采用不同MySQL编码LATIN1和UTF8的兼容
- pwnable.kr cmd2之write up