当前位置: 首页 > news >正文

题解:P9468 [EGOI 2023] Candy / 糖果

P9468 [EGOI 2023] Candy / 糖果

题目描述


在伊卡古城,据说有一座宫殿,其财富超乎想象。在其中,一个走廊中有 NNN 盒来自世界各地的糖果。路过的旅行者只要用黄金支付糖果的重量,就可以拿走任意多的糖果。

装糖果的盒子被从左到右编号为 000N−1N-1N1。在盒子 iii 中,剩余有 aia_iai 单位的糖果,其中 aia_iai 是一个非负整数。

作为宫殿的守护者,你需要移动这些盒子,使得有很多糖果的盒子更靠近入口。

你已知数组 a0,a1,⋯,aN−1a_0,a_1,\cdots,a_{N-1}a0,a1,,aN1,以及整数 FFFTTT。在一次操作中,你被允许交换 a0,a1,⋯,aN−1a_0,a_1,\cdots,a_{N-1}a0,a1,,aN1 中的任意两个相邻元素。要使得数组前 FFF 个元素的和至少为 TTT,至少需要多少次操作?

输入格式


第一行三个整数 N,F,TN,F,TN,F,T

\第二行 NNN 个整数 a0,a1,⋯,aN−1a_0,a_1,\cdots,a_{N-1}a0,a1,,aN1
\

输出格式


如果不可能达成目标,输出 NO

否则,输出一个整数,表示最少操作数。
\

输入 #1

6 2 27
10 4 20 6 3 3

输出 #1

1

输入 #2

6 5 5000000000
1000000000 1000000000 0 1000000000 1000000000 1000000000

输出 #2

3

输入 #3

3 2 100
20 30 60

输出 #3

NO

输入 #4

1 1 100
100

输出 #4

0

说明/提示


样例 111 解释

在样例 111 中,前两个元素的和应当至少为 272727。一次相邻元素的交换就可以达成目标:交换 444202020。在这次交换后,数组变成 10 20 4 6 3 3,前两个元素的和为 10+20=30≥2710+20=30\ge 2710+20=3027



样例 222 解释

在样例 222 中,这个 000 必须一路移动到数组末尾;这需要 333 次交换。


样例 333 解释

在样例 333 中,不可能使得前两个元素和至少为 100100100;我们能做到的最好结果是 60+30=9060+30=9060+30=90


数据范围

对于全部数据,1≤N≤1001\le N\le 1001N1001≤F≤N1\le F\le N1FN0≤T≤10110\le T\le 10^{11}0T10110≤ai≤1090\le a_i\le 10^90ai109
\

  • 子任务一(666 分):N≤2N\le 2N2ai≤100a_i\le 100ai100T≤109T\le 10^9T109
  • 子任务二(191919 分):ai≤1a_i\le 1ai1
  • 子任务三(161616 分):N≤20N\le 20N20
  • 子任务四(303030 分):ai≤100a_i\le 100ai100
  • 子任务五(292929 分):无特殊限制。

提示

答案可能不在 323232 位整型范围内,如果你使用 C++ 语言,请注意溢出的可能。

有一个很妙的思路,分享一下。

根据题目的意图,我们要在移动距离最短前提下,使得数组的前 FFF 个元素的和大于等于 TTT。显然只能从后往前移动,不然无意义。

设选中的 FFF 个元素在原数组中的位置为 x1≤x2≤⋯≤xFx_1 \leq x_2 \leq \dots \leq x_Fx1x2xF,经过交换后在前 FFF 个位置的最终位置为 y1<y2<⋯<yFy_1 < y_2 < \dots < y_Fy1<y2<<yF(其中 yi∈[1,F]y_i \in [1,F]yi[1,F])。

将元素从 xix_ixi 移动到 yiy_iyi 需要 ∣xi−yi∣|x_i - y_i|xiyi 次相邻交换,总交换次数即为 ∑i=1F(xi−yi)\sum\limits_{i=1}^F (x_i - y_i)i=1F(xiyi),因为 xi≥yix_i \geq y_ixiyi

显然不管怎么交换,原来位置和 ∑xi\sum x_ixi 一定等于交换后的位置和 ∑yi\sum y_iyi 加上交换时移动的距离(就是交换次数)

设交换次数为 ttt,则 $ \sum x_i = \sum y_i + t$,移项可得 t=∑xi−∑yit = \sum x_i - \sum y_it=xiyi

可得对于前 FFF 个位置,yiy_iyi 固定取 1,2,3,…F1,2,3,\dots F1,2,3,F,位置和等于 F(F+1)2\frac{F(F+1)}{2}2F(F+1)

所以,最小交换次数的计算方法如下:

t=∑xi−F(F+1)2t=\sum x_i - \frac{F(F+1)}{2} t=xi2F(F+1)

要使得交换次数 ttt 最小,就要使得 ∑xi\sum x_ixi 尽可能小。


所以,我们要选中 FFF 个数值总和大于等于 TTT 的数,在数值总和都大于等于 TTT 时就让位置和最小。

不难想到这一步可以用 dp 解决。设 dpi,j,kdp_{i,j,k}dpi,j,k 表示当前在位置 iii,选了 jjj 个元素,选中的所有元素下标和为 kkk 时的最大数值总和。

转移方程比较简单,只要对于每个不同的元素 iii,尝试加入之前不同的状态就行了:

dpi,j,k=max⁡{dpi−1,j−1,k−i+ai}(j≤min⁡{i,F})dp_{i,j,k} = \max\{ dp_{i-1,j-1,k-i} + a_i \}\ (j \le \min\{i,F\}) dpi,j,k=max{dpi1,j1,ki+ai} (jmin{i,F})

转移时可以滚动数组,不过要倒序枚举 jjj

时间复杂度约为 O(5000×nF)O(5000 \times nF)O(5000×nF)100(100+1)2=5050\frac{100(100+1)}{2}=50502100(100+1)=5050)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll N, F, T;
ll a[105], dp[105][5100]; // dp[j][k]:(当前第i个数)选了j个,下标和为k时,数值和的最大值void solve()
{cin >> N >> F >> T;for(int i = 1; i <= N; i ++){cin >> a[i];}memset(dp, -0x3f, sizeof dp);dp[0][0] = 0;for(int i = 1; i <= N; i ++){for(int j = min(1LL*i, F); j >= 1; j --){for(int k = i; k <= 5050; k ++){ // 100*(100+1)/2 = 5050dp[j][k] = max(dp[j][k], dp[j - 1][k - i] + a[i]);}}}int minp = 1e9;for(int k = 0; k <= 5050; k ++){if(dp[F][k] >= T) minp = min(minp, k);}if(minp == 1e9) puts("NO"); else cout << max(0LL, 1LL*minp - F*(F+1)/2) << '\n';
}signed main()
{ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}
http://www.lryc.cn/news/597190.html

相关文章:

  • 亚马逊云科技 上海AI研究院 突然解散 | AI早报
  • Taint Bug (污点漏洞):
  • GitHub 趋势日报 (2025年07月22日)
  • Docker 基础概念
  • 解决Node 17+版本与Metro、Webpack等兼容性问题(500)
  • 数据结构自学Day13 -- 快速排序--“分而治之”
  • ITIL 4:云计算与微服务对组织架构的影响
  • kotlin基础【1】
  • android studio(NewsApiDemo)100%kotlin
  • 【前端】当前主流的 CSS 预处理器语言Sass / SCSS、Less、Stylus
  • kotlin基础【2】
  • BaaS平台(Supabase)
  • 数据结构自学Day13 -- 快速排序--“前后指针法”
  • 《计算机网络》实验报告六 电子邮件
  • 数据结构(2)顺序表算法题
  • 【数据结构】二叉树的链式结构--用C语言实现
  • 数据结构系列之AVL树
  • Java冒泡排序的不同实现
  • Excel自动分列开票工具推荐
  • 耐达讯自动化EtherCAT转RS232:示波器连接的“开挂秘籍”
  • IDEA如何管理多个Java版本。
  • 图机器学习(16)——图数据与自然语言处理
  • 使用idea 将一个git分支的部分记录合并到git另一个分支
  • idea部署新项目时,用自定义的maven出现的问题解决
  • 【网络编程】二、socket编程
  • Excel 将数据导入到SQLServer数据库
  • Linux文件——Ext2文件系统(3)_软硬链接
  • Encore.ts:下一代高性能 TypeScript 后端框架的崛起
  • Qt(基本组件和基本窗口类)
  • 开源深度学习新宠:Burn框架助您无忧高效建模