首页 > 代码库 > SGU 410 Galaxy in danger --贪心，想法题

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

2024-07-14 22:06:39   220人阅读

题意：有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 100007int a[N];int backdouble[5003][2];int predouble[5004];int main(){    int n,i,j,maxi = 0,kb,kp,ans = 0,flag = 1;    scanf("%d",&n);    for(i=1;i<=n;i++)    {        scanf("%d",&a[i]);        if(a[i] == 0)            flag = 0;        maxi = max(maxi,a[i]);    }    if(!flag)    {        puts("0");        return 0;    }    kb = kp = 0;    for(i=1;i<=n;i++)    {        if(a[i] == maxi)            continue;        int tmp = a[i];        while(tmp < maxi)        {            if(maxi+ans <= 1000)  //还能输出            {                if(2*tmp<=maxi && kp <= 1000)                    predouble[kp++] = i;                else                {                    backdouble[kb][0] = i;                    backdouble[kb++][1] = 2*(maxi-tmp);                }            }            tmp *= 2;            ans++;        }    }    printf("%d\n",maxi+ans);    if(ans+maxi > 1000)        return 0;    for(i=0;i<kp;i++)        printf("science mission to the planet %d\n",predouble[i]);    for(i=maxi;i>0;i--)    {        for(j=0;j<kb;j++)            if(backdouble[j][1] == i)                printf("science mission to the planet %d\n",backdouble[j][0]);        puts("flying mission");    }    return 0;}
View Code

 


联系
我们