SGU 410 Galaxy in danger --贪心，想法题

题意：有n个星球，每个星球有Ai个人，每次有两种选择，第一是从每个星球上去掉1个人，第二个选择是选择一个星球放置一个科学家，将该星球的人数加倍，问最少多少次能够将所有星球上的人数同时变为0，并且如果步数<=1000，还要输出操作顺序。

解法：找出人数最多的那个星球，设最大人数为maxi，那么跑一个循环，每次该星球如果人数<maxi，那么能加倍就加倍到离maxi最近的位置，然后计算他们的差，比如2 1035，加倍后为1024 1035，差为11，那么到时候1024减到11的时候，1035变成了22，那么这个时候马上加倍11，再减即可。每个不等于最大人数的星球上都这样处理即可。predouble[]记录处理前先要加倍到离最大数最近的位置的星球，backdouble[]记录减到差值的时候要加倍的星球。然后输出即可。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define N 100007

int a[N];

int backdouble[][];

int predouble[];

int main()

{

    int n,i,j,maxi = ,kb,kp,ans = ,flag = ;

    scanf("%d",&n);

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

    {

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

        if(a[i] == )

            flag = ;

        maxi = max(maxi,a[i]);

    }

    if(!flag)

    {

        puts("");

        return ;

    }

    kb = kp = ;

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

    {

        if(a[i] == maxi)

            continue;

        int tmp = a[i];

        while(tmp < maxi)

        {

            if(maxi+ans <= )  //还能输出

            {

                if(*tmp<=maxi && kp <= )

                    predouble[kp++] = i;

                else

                {

                    backdouble[kb][] = i;

                    backdouble[kb++][] = *(maxi-tmp);

                }

            }

            tmp *= ;

            ans++;

        }

    }

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

    if(ans+maxi > )

        return ;

    for(i=;i<kp;i++)

        printf("science mission to the planet %d\n",predouble[i]);

    for(i=maxi;i>;i--)

    {

        for(j=;j<kb;j++)

            if(backdouble[j][] == i)

                printf("science mission to the planet %d\n",backdouble[j][]);

        puts("flying mission");

    }

    return ;

}