CF-1013-D. Simple Permutation · znzryb
## 思路讲解
其实想明白了就很简单，就是这个就是平均数（向上取整），那么就找离平均数最近的素数就行，然后让这个数列的上界平均数不断是这个素数就行。
## AC代码
::: 源代码
```cpp
// Problem: D. Simple Permutation
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
ll N,M,T;
bool isPrime[MAXN];
vector<ll> primes;
set<ll> perm;
bool inAns[MAXN];
inline ll ceilDiv(ll x,ll cnt){
return ceil(x*1.0l/cnt);
}
inline void genPrime(){
for(int i=2;i<=MAXN-5;++i){
isPrime[i]=true;
}
for(int i=2;i*i<=MAXN-5;++i){
if(isPrime[i]){
for(int j=2*i;j<=MAXN-5;j+=i){
isPrime[j]=false;
}
}
}
for(int i=2;i<=MAXN-5;++i){
if(isPrime[i]) primes.pb(i);
}
}
inline void solve(){
cin>>N;
vector<ll> ans;
perm.clear();
for(int i=1;i<=N;++i){
perm.insert(i);
inAns[i]=false;
}
ll cnt=1,sum=0;
// for(int i=SZ(primes)-1;i>=0;--i){
// if(SZ(ans)>=N/3-1) break;
// ll curP=primes[i];
// while(true){
// if(SZ(ans)>=N/3-1) break;
// ll l=(curP-1)*cnt-sum; // 其实是下界
// // #ifdef LOCAL
// // cerr << l << '\n';
// // #endif
// auto it=perm.lower_bound(l+1);
// if(it==perm.end()) break;
// ll num=*it;
// if(ceilDiv(num+sum,cnt)==curP){
// ans.pb(num);
// ++cnt;
// sum+=num;
// inAns[num]=true;
// perm.erase(it);
// }else{
// break;
// }
// }
// }
ll curP=*lower_bound(all(primes),N/2);
while(true){
// if(SZ(ans)>=N/3-1) break;
ll l=(curP-1)*cnt-sum; // 其实是下界
// #ifdef LOCAL
// cerr << l << '\n';
// #endif
auto it=perm.lower_bound(l+1);
if(it==perm.end()) break;
ll num=*it;
if(ceilDiv(num+sum,cnt)==curP){
ans.pb(num);
++cnt;
sum+=num;
inAns[num]=true;
perm.erase(it);
}else{
break;
}
}
// #ifdef LOCAL
// cerr << ans.size() << '\n';
// #endif
for(int i=0;i<ans.size();++i){
cout<<ans[i]<<" ";
}
for(int i=1;i<=N;++i){
if(!inAns[i]) cout<<i<<" ";
}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
genPrime();
// #ifdef LOCAL
// for(int i=0;i<primes.size();++i){
// cerr<<primes[i]<<" ";
// }
// cerr<<"\n";
// #endif
while(T--){
solve();
}
// solve();
return 0;
}
/*
WA https://codeforces.com/contest/2090/submission/316398539
AC https://codeforces.com/contest/2090/submission/316487010
*/
```
:::
## 心路历程（WA，TLE，MLE……）
[https://codeforces.com/contest/2090/submission/316398539](https://codeforces.com/contest/2090/submission/316398539)
其实还可以，过了8个点，但是在面对大数的情况时力不从心。
::: 错误代码1
```cpp
// Problem: D. Simple Permutation
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
ll N,M,T;
bool isPrime[MAXN];
vector<ll> primes;
set<ll> perm;
bool inAns[MAXN];
inline ll ceilDiv(ll x,ll cnt){
return ceil(x*1.0l/cnt);
}
inline void genPrime(){
for(int i=2;i<=MAXN-5;++i){
isPrime[i]=true;
}
for(int i=2;i*i<=MAXN-5;++i){
if(isPrime[i]){
for(int j=2*i;j<=MAXN-5;j+=i){
isPrime[j]=false;
}
}
}
for(int i=2;i<=MAXN-5;++i){
if(isPrime[i]) primes.pb(i);
}
}
// inline ll bsearch(ll sum,ll cnt){
// ll l=1,r=mod;
// while(l<r){
// ll mid=l+r+1>>1;
// if(ceilDiv(mid,sum,cnt)<=3){
// l=mid;
// }else{
// r=mid-1;
// }
// }
// return l;
// }
inline void solve(){
cin>>N;
vector<ll> ans;
perm.clear();
for(int i=1;i<=N;++i){
perm.insert(i);
inAns[i]=false;
}
ll cnt=1,sum=0;
for(int i=0;i<primes.size();++i){
if(ans.size()>=N) break;
ll curP=primes[i];
while(true){
if(ans.size()>=N) break;
ll l=(curP-1)*cnt-sum; // 其实是下界
// #ifdef LOCAL
// cerr << l << '\n';
// #endif
auto it=perm.lower_bound(l+1);
if(it==perm.end()) break;
ll num=*it;
if(ceilDiv(num+sum,cnt)==curP){
ans.pb(num);
++cnt;
sum+=num;
inAns[num]=true;
perm.erase(it);
}else{
break;
}
}
}
#ifdef LOCAL
cerr << ans.size() << '\n';
#endif
for(int i=0;i<ans.size();++i){
cout<<ans[i]<<" ";
}
for(int i=1;i<=N;++i){
if(!inAns[i]) cout<<i<<" ";
}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
genPrime();
// #ifdef LOCAL
// for(int i=0;i<primes.size();++i){
// cerr<<primes[i]<<" ";
// }
// cerr<<"\n";
// #endif
while(T--){
solve();
}
// solve();
return 0;
}
/*
*/
```
:::