ACM-zoj3789-排列利用

点击量:27


利用排列找规律。

首先利用next_permutation函数进行求排列

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int a[30];
int cal(int n)
{
    int sum = 0;
    int i;
    for (i = 1; i <= n; i++) {
        /* code */
        sum = abs(sum - a[i]);
    }
    return sum;
}
void parray(int a[], int len)
{
    int i;
    for (i = 1; i <= len; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}
void cp(int a[], int b[], int n)
{
    int i;
    for (i = 0; i <= n; i++) {
        a[i] = b[i];
    }
}
int main(int argc, const char *argv[])
{
    int i;
    for (i = 1; i <= 30; i++) {
        a[i] = i;
    }
    int n;
    int maxa[30], mina[30];
    while (~scanf("%d", &n)) {
        int max = -INF;
        int min = INF;
        if (n == 1) {
            cout << "1 1" << endl;
            cout << "1" << endl << "1" << endl;
            continue;
        }
        while (next_permutation(a+1, a+n+1)) {
            /* code */
            int temp = cal(n);
            if (temp >= max) {
                max = temp;
                cp(maxa, a, n);
            }
            if (temp <= min) {
                min = temp;
                cp(mina, a, n);
            }
        }
        cout << min << " " << max << endl;
        for (i = 1; i <= n; i++) {
            cout << mina[i] << " ";
        }
        cout << endl;
        for (i = 1; i <= n; i++) {
            cout << maxa[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

代码如上。

可以观察出规律,然后即可AC。

详细代码下次再写= =

AC代码

#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;
int main()
{
    int i, n;
    int max, min;
    while(~scanf("%d", &n))
    {
        max = min = 0;
        for(i = n; i >= 1; i--)
            min = abs(min - i);
        for(i = n-1; i >= 1; i--)
            max = abs(max - i);
        max = abs(max - n);
        printf("%d %d\n", min, max);
        for(i = n; i >1 ; i--)
            printf("%d ", i);
        puts("1");
        for(i = n-1; i >= 1; i--)
            printf("%d ", i);
        printf("%d\n", n);
    }
    return 0;
}

规律在代码中,很明确。

发表评论

电子邮件地址不会被公开。 必填项已用*标注