MENU

Slava and tanks | ACM

May 2, 2019 • ACM

题目大意给出一个一维数组作为线性地图,每一个格都有着未知数量的坦克,我们需要从空中扔炸弹将坦克全部摧毁
已知坦克承受两次炸弹攻击就会被摧毁,坦克每次被击中会随机向相邻的格子移动
问最少需要多少炸弹才可以摧毁全部坦克,及炸弹的轰炸顺序
输入数据第一行包含一个整数N(2≤  N  ≤100 000) -在地图的大小。
数据输出在第一行打印m - 我们销毁所有坦克需要的最小数量的炸弹。
在第二行中,打印m个整数$k_1$,$k_2$,$k_3$...$k_m$。数字$k_m$表示第m个炸弹应该落在单元$k_m$处。
样例输入2
样例输出3
2 1 2
样例输入3
样例输出4
2 1 3 2

思路简述

  • 我觉得这道题超级水,但是一开始还是没做出来。无论是因为时间还是什么
  • 首先,每辆坦克只能承受两次伤害,为了让我们的炸弹效果最大化,我们应该是隔一个扔一枚炸弹
  • 例如,第一轮在1,3,5位置扔炸弹,第二轮在2,4,处扔炸弹,第三轮在1,3,5位置扔炸弹,至此所有坦克已被摧毁。
  • 思路很简单,但是涉及到一个单双数的问题。
  • 如果是单数的话,要确保最中间的格子在第一轮被轰炸,才可以做到使用的炸弹数量最少。如N=3,要确保顺序是 2 , 1 3 , 2 而不是1 3 ,2 ,1 3 。
#include<stdio.h>
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(n%2 == 0)
            printf("%d\n",n/2*3);
        else
            printf("%d\n",n/2*3+1);
        for(int i = 2;i <= n;i+=2)
            printf("%d ",i);
        for(int i = 1;i <= n;i+=2)
            printf("%d ",i);
        for(int i = 2;i <= n;i+=2)
            printf("%d ",i);
        printf("\n");
    }
    return 0;
}
Archives QR Code
QR Code for this page
Tipping QR Code