Great Inversion 逆序数、构造
Source
The 13th UESTC Programming Contest Preliminary
My Solution
本来是用贪心法，如果填一个个数就够那么填上去然后返回，如果不够则把m填在第一位，然后n--，m--，k -= n;然后递归下去，然后判断不可能的
情况返回-1， 同时输入时 n == 1 || m == 1则直接输出 -1；
然后一直WA9就交给队友做了
后来才发现我的方法的构造出的最多的k不够大 比如 5 5 5 4 3 2 1 1 比 5 4 3 2 1 1 1 1 的逆序数多
然后后来重新用构造法写了一个暴力的，虽然写着k最大1e6，其实k对多四十多万，不会超时
1、先贴上前面写的贪心法，WA的
/* Yesterday I get many WA9, my max k is smaller than the right answer.
#include
#include
#include
#define LOCAL
using namespace std;
const int maxn = 1000+8;
int lis[maxn], m, n, cnt = 0, noans = -1;
int a[maxn];
void dfs(int x,int k,int len) //[x, n]
{
if(x >= n) return; //it is equal of //if(len < 0) return;
if(k < len){lis[n-k] = m;return;} //if k == 0, it's also okay
lis[x] = m; m--;
len--;
//if(len < 0) return;
k = k - len;
x++;
if((m == 1 && k != 0 && len != 0) || (len == 1 && k != 0)) {noans = 1;return;}
dfs(x, k, len);
}
int main()
{
#ifdef LOCAL
freopen("a.txt", "r", stdin);
//freopen("b.txt", "w", stdout);
#endif // LOCAL
memset(lis, -1, sizeof lis);
int k;
scanf("%d%d%d", &n, &m, &k);
//int o = 1;
//for(int i = 1; o <= 100000; i++) // printf("a[%d] = %d;", i, o*=i); //if(n >= m)
if(m == 1 || n == 1) {printf("-1");} //if n == 1 , ans is -1
else {
dfs(1,k,n);
if(noans == 1) {printf("-1");}
else {
if(lis[1] != -1)printf("%d", lis[1]);
else printf("1");
for(int i = 2; i <= n; i++){
if(lis[i] != -1)printf(" %d", lis[i]);
else printf(" 1");
}
}
}
return 0;
}
*/
2、然后是正确的做法，用构造法虽然运行不快(能过了)但写起来方便(虽然没有上面的方便，但正确☺☺)
先构造出正序的数列，最大的比最小的最多相差1，所以分两批构造
t = n / m;
t1 = n - t * m;
然后前t1个数是每个数出现t+1次，后面的数出现t次。 然后因为要分两次构造，主要是控制好下标
开始find the ans ,每次如果 lis[i] < lis[i+1] 则swap(,)然后x++，并且判断如果x == k可以返回，
直到读完一遍然后递归再读一遍，并在每次判断上一遍有没有x++的情况，如果没有说明已经到x max 但小于 k返回 false
#include
#include
//#define LOCAL
using namespace std;
const int maxn = 1000+8;
int lis[maxn], m, n, cnt = 0, noans = -1;
int k, x = 0;
bool judge = false;
bool findtheans() //[x, n]
{
if(x == k) return true;
for(int i = 1; i <= n; i++){
if(lis[i] < lis[i+1]) {swap(lis[i], lis[i+1]);x++;if(x == k) return true;if(!judge) judge = true;}
}
if(judge) {judge = false;findtheans();}
else if(x != k) return false;
}
int main()
{
#ifdef LOCAL
freopen("a.txt", "r", stdin);
//freopen("b.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d%d", &n, &m, &k);
//build the array
int t = n / m;
int t1 = n - t*m;
for(int i = 1; i <= t1; i++){
for(int j = 1; j <= t+1; j++)
lis[(i-1)*(t+1)+j] = i;
}
for(int i = t1+1; i <= m; i++){
for(int j = 1; j <= t; j++)
lis[t1*(t+1)+(i-(t1+1))*t+j] = i; //(i-(t1+1))*t 回到最初计数个数
}
if(m == 1 || n == 1) {printf("-1");} //if n == 1 , ans is -1
else {
if(!findtheans()) {printf("-1");} //use the function here
else {
printf("%d", lis[1]);
for(int i = 2; i <= n; i++){
printf(" %d", lis[i]);
}
}
}
return 0;
}非特殊说明，本博所有文章均为博主原创，未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
- THE END -
最后修改：2024年11月15日
非特殊说明，本博所有文章均为博主原创，未经许可不得转载。
如经许可后转载，请注明出处：https://prolightsfxjh.com/article/uestc-1040-great-inversion/
共有 0 条评论