哪里可以做拍卖网站,代码编程教学入门软件,怎么用本机做服务器发布网站,一键生成app软件下载题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/1080/B 来源#xff1a;牛客网
tokitsukaze有n个数#xff0c;需要按顺序把他们插入哈希表中#xff0c;哈希表的位置为0到n-1。
插入的规则是#xff1a; 刚开始哈希表是空的。 对于一个数x
链接https://ac.nowcoder.com/acm/contest/1080/B 来源牛客网
tokitsukaze有n个数需要按顺序把他们插入哈希表中哈希表的位置为0到n-1。
插入的规则是 刚开始哈希表是空的。 对于一个数x在哈希表中如果(x mod n)的位置是空的就把x放在(x mod n)的位置上。如果不是空的就从(x mod n)往右开始找到第一个空的位置插入。若一直到n-1都不是空的就从位置0开始继续往右找第一个空的位置插入。
因为哈希表总共有n个空位需要插入n个数所以每个数都能被插入。
现在tokitsukaze想知道把这n个数按顺序插入哈希表后哈希表中的每个位置分别对应的是哪个数。
输入描述:
第一行包含一个正整数n(1≤n≤10^6)。
第二行包含n个非负整数x(0≤x≤10^9)这些数按从左到右的顺序依次插入哈希表。
输出描述:
输出一行n个数第i个数表示哈希表中位置为i所对应的数。(0≤i≤n-1)
示例1
输入
复制
4
1 2 6 5输出
复制
5 1 2 6说明
插入1时1 mod 41是空的在位置1插入。
插入2时2 mod 42是空的在位置2插入。
插入6时6 mod 42不是空的找到下一个空的位置为3所以在位置3插入。
插入5时5 mod 41不是空的找到下一个空的位置为0所以在位置0插入。
示例2
输入
复制
4
3 0 7 11输出
复制
0 7 11 3说明
插入3时3 mod 43是空的在位置3插入。
插入0时0 mod 40是空的在位置0插入。
插入7时7 mod 43不是空的找到下一个空的位置为1所以在位置1插入。
插入11时11 mod 43不是空的找到下一个空的位置为2所以在位置2插入。
解题报告 这题做法不少可以直接set维护第一个空位二分查找即可。 还可以用并查集维护空位每次在x位置插入数后合并x和(x1)%n也不难写。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e6 5;
setint ss;
int ans[MAX];
int main()
{int n;cinn;for(int i 0; in; i) ss.insert(i);for(int x,i 1; in; i) {scanf(%d,x);auto it ss.lower_bound(x%n );if(it ss.end()) ans[*ss.begin()] x,ss.erase(ss.begin());else ans[*it] x,ss.erase(it);}for(int i 0; in; i) printf(%d%c,ans[i],i n-1 ? \n : );return 0 ;
}
附一个并查集代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e6 5;
int f[MAX];
int getf(int v) {return f[v] v ? v : f[v] getf(f[v]);
}
void merge(int u,int v) {int t1 getf(u),t2 getf(v);f[t1] t2;
}
int ans[MAX];
int main()
{int n;cinn;for(int i 0; in; i) f[i] i;for(int x,i 1; in; i) {scanf(%d,x);int pos x%n;int fa getf(pos);ans[fa] x;merge(fa,(fa1)%n);}for(int i 0; in; i) printf(%d%c,ans[i],i n-1 ? \n : );return 0 ;
}
