企业官网建设流程全解析

题目描述

给定一个长度为 n 的序列 b，要求构造出另一个长度为 n 的序列 a，使得对于新序列中每个元素 ai​，满足 ai​ 在 a 中的出现次数恰好为 bi​。要求 1≤ai​≤n。

输入格式

本题有多组测试数据。

第一行一个正整数 T(1≤T≤104) 表示测试数据数量。

随后 2T 行，第 i+1 至 i+2 行为第 i 组测试数据。第 i+1 行一个整数 n(1≤n≤2⋅105)，表示 b 的长度，第二行 n 个整数 bi​(1≤bi​≤n)，表示 b 序列。

保证 n 的总和不超过 2⋅105。

输出格式

输出答案。若有多个答案，输出任意一个均可。如果不存在答案，输出-1。

输入输出样例

输入 #1复制

3 4 1 2 3 4 6 1 2 2 3 3 3 6 6 6 6 6 6 6

输出 #1复制

-1 4 5 5 6 6 6 2 2 2 2 2 2

说明/提示

在第一组测试数据中，没有一个数组 a 符合要求。

在第二组测试数据中， 4,5,6 分别出现了 1,2,3 次，所以 a={4,5,5,6,6,6} 符合要求。

#include "bits/stdc++.h" #define int long long using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //这个记得注释掉 //freopen("../input.txt","r",stdin); int t; cin>>t; while (t--) { //cout<<"------------------------\n"; int n; cin>>n; vector<int>a(n); int maxn=0; for (int i=0;i<n;i++) { cin>>a[i]; maxn=max(a[i],maxn); } //邻接表存每个数字出现在哪些位置 //g[val].push_back(idx); vector<vector<int>>g(maxn+1); for (int i=0;i<n;i++) { g[a[i]].push_back(i); } vector<int>ans(n); bool ok=true;//记录有没有解 int cur=1;//当前填充的数字 //枚举每一种值 for (int val=1;val<=maxn;val++) { //val在原数组里出现了多少次 int cnt=g[val].size(); //判断能不能被完整分组 if (cnt%val==0) { for (int i=0;i<cnt;i++) { //把这些位置每val个分成一组 //然后让同一组在答案数组里填同一个数 ans[g[val][i]]=cur+i/val; } cur+=cnt/val;//更新填充的数字 } else { ok=false; break; } } if (ok) { for (auto e:ans) cout<<e<<" "; cout<<"\n"; } else cout<<"-1\n"; } return 0; }