题意:有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 ;
}
04-14 23:15