我要招人

去企业版

首页 > 试题广场 >

小苯的刷怪笼

[编程题]小苯的刷怪笼

热度指数：1211 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 小苯为了阻止小红继续前进，选择将 $n$ 个怪物排成一排来阻挡他，这些怪物的血量之和为 $a$ ，小苯可以随意分配他们的血量（不能为 $0$ ）。

$\hspace{15pt}$ 小红的每次攻击可以使一个或相邻的两个怪物血量减 $1$ 。当怪物的血量小于等于 $0$ 时，怪物被消灭（怪物被消灭后依然存在，相邻关系不会被改变）。

$\hspace{15pt}$ 小红一定会选择最优策略，使用尽可能少的攻击次数消灭这些怪物。在这种情况下，小苯希望小红能使用恰好 $k$ 次攻击消灭所有的怪物。

$\hspace{15pt}$ 请你帮小苯找出一个可能的血量分配方案。

输入描述:

第一行输入三个整数  。

输出描述:

如果无解，请输出  。否则输出  个正整数，按顺序代表怪物的血量。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测功能可能因此返回答案错误结果，请自行检查答案正确性。

示例1

输入

3 8 5

输出

3 3 2

示例2

输入

3 10 1

输出

-1

算法知识视频讲解

Java

牛客203596504号

首先我们分析总量关系：
假设题面两种操作次数为op1和op2，显然有k=op1+op2和a=op1+2*op2
方程求解得到：op1=2*k-a和op2=a-k
操作次数不能为负，所以有解条件k<=a<=2k

作为构造题，初始状态不明确，但结束状态是明确的，所以我们可以反推。
初始时所有血量都大于0，结束时所有血量都是0，那我们给每个怪物分配1点保底
分配后状态是[1,1,1,1,……,1,1,1,1]，总血量还剩a-n

如果n是奇数，op1=1，op2=floor(n/2)，如果n是偶数，op1=0，op2=floor(n/2)

特别注意，“小红一定会选择最优策略”，意味着小红会尽可能使用op2操作，除非无法操作。
所以我们要利用op2操作“必须相邻”的限制。办法就是，把op1操作放在最前，把op2操作放在最后
构造状态：[x,1,1,1,……,1,1,y,y]，现在只需算出x和y的值就可以解决了。
如果n是偶数，x中要抽出1个与第2位配对，所以x=1+op1=1+2*k-a
如果n是奇数，后面的全都配对了，只剩下孤零零的x=op1=2*k-a
根据总血量a=x+(n-3)+2*y就能推算出y=1+a-k-floor(n/2)
得解。（有解的前提条件是x>0且y>0）

但是这道题到此并未结束，我们还要处理一下边界：
n=4时，[x,1,y,y]，很好没问题
n=3时，[x,y,y]，很好没问题
n=2时，只有两个数，一个大一个小，要k次耗完血量，所以大的必须是k，小的是a-k

n=1时，只有一个数，毫无疑问，只有a=k才能有解。

代码如下：

if (n == 1) {
    System.out.print(k == a ? a : "-1\n");
} else if (a <= k || a > 2 * k) {
    System.out.print("-1\n");
} else if (n == 2) {
    System.out.print((a - k) + " " + k + "\n");
} else {
    int y = 1 + a - k - (n / 2);
    if (y <= 0) {
        System.out.print("-1\n");
        return;
    }
    int x = 2 * k - a;
    if ((n & 1) == 0) x++;
    char[] cs = new char[2 * (n - 3)];
    for (int i = 0; i < cs.length;) {
        cs[i++] = ' ';
        cs[i++] = '1';
    }
    StringBuilder sb = new StringBuilder();
    sb.append(x).append(cs).append(' ').append(y).append(' ').append(y);
    System.out.print(sb); // x 1 ... 1 y y
}

发表于 2026-05-19 06:18:42 回复(0)

提交观点

问题信息

难度：

2条回答 5收藏 75浏览

小苯的刷怪笼

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

相关试题