Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

门上有着N个宝珠，每个宝珠都有一个数字。Mini询问老者后，得知要想打开这扇门，就得找出两颗珠宝，使这两颗珠宝撞在一起

后产生的能量值最接近123。

两颗珠宝撞在一起以后产生的能量值的计算方法是：将两个珠宝所代表的数字转换为7进制的数后，一一对照这两个七进制数的

每一位，若相同，则结果为0否则为1。

如：两颗珠子所代表的数为18和370，将这两个数转化为7进制后是24和1036，对于高位不足的数，采取高位添‘0’的方法，即两个

数为0024，1036。最后得到的能量值C为1011，再将C当作二进制数转换为十进制数。那么转换后的C就为这两个珠撞在一起以后

所产生的能量值。

【样例说明】

370和78这两颗宝珠所产生的能量值15最接近123

【输入格式】

第一行一个数N，表示宝珠的数量。（2<=N<=900） 第二行N个数，每个数用空格隔开，每个数表示第I个宝珠所代表的数字(0<=每个数<=11111)

【输出格式】

一个数，代表你所找到的最接近123的能量值

Sample Input

5

18 370 45 36 78

Sample Output

15

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t066

【题解】



O(N^2)枚举两个珠宝;

按照所给规则尝试合并它们;

10进制转7进制;

两个7进制根据相同为0,不同为1的规则转成一个2进制;

然后2进制转成10进制;

看看是不是和123的差距更小;更小就更新答案呗.

时间复杂度O（N^2);

(写时间复杂度真的是为了装逼哦[斜眼笑])



【完整代码】

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

#define pb push_back

const int MAXN = 900+100;

int n,a[MAXN];

int ans = -1,t;

vector <int> two;

vector <int> get7(int x)

{

    vector <int> g;

    g.clear();

    while (x>0)

    {

        g.pb(x%7);

        x/=7;

    }

    return g;

}

int main()

{

//    freopen("F:\\rush.txt","r",stdin);

    int now = 1;

    while (now<10e8)

    {

        two.pb(now);

        now <<=1;

    }

    scanf("%d",&n);

    for (int i = 1;i <= n;i++)

        scanf("%d",&a[i]);

    for (int i = 1;i <= n-1;i++)

        for (int j = i+1;j <= n;j++)

        {

            vector<int> x = get7(a[i]),y = get7(a[j]);

            int lenx = x.size(),leny = y.size();

            int len = max(lenx,leny);

            while (int(x.size())<len) x.pb(0);

            while (int(y.size())<len) y.pb(0);

            reverse(x.begin(),x.end());

            reverse(y.begin(),y.end());

            vector<int> v;

            v.clear();

            for (int i = 0;i <= len-1;i++)

                if (x[i]==y[i])

                    v.pb(0);

                else

                    v.pb(1);

            reverse(v.begin(),v.end());

            int xx = 0;

            for (int i = 0;i <= len-1;i++)

                xx+=v[i]*two[i];

            if (ans==-1)

            {

                ans = xx;

                t = abs(ans-123);

            }

            else

            {

                int tt = abs(xx-123);

                if (tt<t)

                {

                    ans = xx;

                    t = tt;

                }

            }

        }

    printf("%d\n",ans);

    return 0;

}