题目链接:CSUSTOJ | 小小新生,可笑可笑 (hard)
你可能无法访问这个链接,因此我在文末附上了完整的题目。
随笔
作为一名已经大二的老学长,我依然坚持参加了今天的校ACM新生赛。一共十道题,我AC了两道。参加比赛和自己平时刷力扣的感受区别很大,题目的侧重点也有所不同,力扣更多的是练习对数据结构的操作(这些练习也很有帮助)。今天比赛的体验一如一年前那般难受,自以为对了,提交却一直Wrong Answer。
比赛时间结束后,我仍对刚刚Wrong Answer的题耿耿于怀,继续肝了2小时(所以这道题写了4小时),终于AC了。不然,我将难以脱离对世界和自我的双重怀疑。
解这道题的思路来自一道力扣题:453. 最小操作次数使数组元素相等,我很快就感受到这两之间的相似之处,这也是一次从情景中抽象出数学问题的体验。然而在我具体实现时,思维总是误入歧途,也常常不小心就把自己未经证实的猜想就当作已知条件。在一些反复的胡乱摸索中,时间就悄悄流逝了。
这道题的体验和我之前写的一道魔方阵很相似,我在寻找数学上的映射关系,我感觉像在做小学数学奥赛题。而那份魔方阵的代码我现在已经看不懂了,因为代码的关键部分是很多计算公式,而我没写注释。
在本文中描述自己的思路时,总感觉很困难,我不知道怎么用文字将它组织起来。可能,我脑袋里的思路本身就有些散乱而缺少组织性?总感觉没写明白。
思路
算法的大致步骤如下:
- 1、排序(从小到大);
- 2、找对齐状态;
- 3、数学计算。
接下来让我们看看更详细的介绍。
chd的npy们的怒气上限是一个数组a,长度为n。那么问题可以这样描述:
每次操作任选a中的n-1个元素,使它们的值减1,同时保证不能有元素减到0,问:最多可以操作多少次?
同时操作多个元素当然不如每次仅需操作一个元素方便,于是我们可以这样描述问题:
每次操作任选a中的1个元素,使它的值加1,同时保证累积操作次数小于a中最小的元素,问:最多可以操作多少次?
找对齐状态
如何能得到前面问题的解?当我们将a中相等元素的数量最大化且操作次数最小化后,就可以很方便地计算出最终的解。下面看个例子。
最初数组a为{4, 5, 6},
4 | 5 | 6 | 操作次数 |
---|---|---|---|
6 | 6 | 6 | 3 |
7 | 7 | 7 | 6 |
设操作次数为h,相等时元素值为k,相等元素的数量为N。则在表格的第二行状态{6, 6, 6}下,h=3,k=6,N=3。我们可以通过表达式
h
=
h
+
(
k
−
h
−
1
)
/
(
N
−
1
)
∗
N
h=h+(k-h-1)/(N-1)*N
h=h+(k−h−1)/(N−1)∗N
一步计算出表格第三行状态{7, 7, 7}时的操作次数。
你可能很疑惑怎么突然就冒出个表达式,这个疑惑我们先放一放。
现在假设你已经知道,在a中相等元素的数量最大化后,我们通过某个表达式一步即可计算出问题的解。那么我们现在要解决的小问题是:
以最小的操作次数使数组a中相等元素数量最大,需要操作多少次?
我们可以先一次遍历,同时记录“从头到当前位置的区间内的数组元素相等”的最小操作次数,得到数组sums。
//作差求和
vector<int> sums;
int sum = nums[1] - nums[0];
sums.push_back(sum);
for(int i = 2; i < n; i++){
sum = sum + (a[i] - a[i-1]) * i;
sums.push_back(sum);
}
对于数组a = {4, 5, 6},我们将得到数组sums = {1, 3}。即想让a中的前面两个元素相等最少需要操作1次,得到{5, 5, 6};而想让a中的前三个元素相等最少需要操作3次,得到{6, 6, 6}。
然后再次遍历,找到相等元素数量最大时操作次数最小的状态,
//找最大对齐状态
int i;
for(i = 0; sums[i] < nums[i+1] && i < n - 1; i++);
i = i - 1;
此时sums[i]即为达到该状态需要的操作次数,而a[i+1]即为该状态下每个元素的值,a中相等元素的数量为i+2。
找到这样一个i后,我们就可以通过表达式直接计算出最终的结果啦!
表达式
还是看这个例子:
4 | 5 | 6 | 操作次数 |
---|---|---|---|
6 | 6 | 6 | 3 |
7 | 7 | 7 | 6 |
很容易观察到,从第二行到第三行操作次数的变化
Δ
h
\Delta h
Δh = 6 – 3 = 3,而3不正是数组元素的数量?
再看下面的例子:
a[0] | a[1] | a[2] | 操作次数 |
---|---|---|---|
9 | 9 | 9 | 1 |
10 | 10 | 10 | 4 |
11 | 11 | 11 | 7 |
12 | 12 | 12 | 10 |
13 | 12 | 12 | 11 |
在我们增加操作次数的过程中,数组a和操作次数h都在变化,这显然是不方便的,为了找到最大的操作次数,我们可能需要一步步地迭代a和h,或者列一个方程得到操作次数的变化量x(N为数组元素数量):
a
+
x
=
h
+
N
∗
x
+
1
a+x=h+N*x+1
a+x=h+N∗x+1
可计算机并不擅长解方程,它比较喜欢计算表达式。但问题不大,我们只需将方程变形一下:
h
=
h
+
(
k
−
h
−
1
)
/
(
N
−
1
)
∗
N
h=h+(k-h-1)/(N-1)*N
h=h+(k−h−1)/(N−1)∗N
但这还不够,通过该表达式计算出来的只是表格第四行的h = 10。我们可以观察到,此时数组元素的值为12,而最大操作次数正是
12
−
1
=
11
12-1=11
12−1=11,因此我们可以补个if
判断:
step = (k - h - 1) / (N - 1); //下一步计算h会更新,这里是做个备份
h = h + (k - h - 1) / (N - 1) * N; //前面推出的公式
if(h < k + step - 1){
h = k + step - 1;
}
如果你能看到这里,你应当已经大致知道如何解决这个问题了!
前面的例子中,都将数组a中所有元素变得相同了,但有时想让a中所有元素相同会导致超过限制的操作次数。
a[0] | a[1] | a[2] | 操作次数 |
---|---|---|---|
2 | 4 | 7 | 0 |
4 | 4 | 7 | 2 |
5 | 5 | 7 | 4 |
7 | 7 | 7 | 8 |
如果是{7, 7, 7},就不满足“操作次数小于数组a中的最小值”。我们只能退一步,让前面两个元素相同,即{4, 4, 7}。然后同样可以使用前面的表达式计算出
h
=
4
h = 4
h=4,即表格第三行的状态。
代码实现-cpp
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
//输入并排序
int n;
cin >> n;
vector<int> nums;
int max = -1;
for(int i = 0; i < n; i++){
int t;
cin >> t;
nums.push_back(t);
if(t == 0){
printf("0\n");
return 0;
}
}
sort(nums.begin(), nums.end());
//一直活下去
if(nums.size() <= 1){
printf("INF\n");
return 0;
}
//作差求和
vector<int> sums;
int sum = nums[1] - nums[0];
sums.push_back(sum);
for(int i = 2; i < n; i++){
sum = sum + (nums[i] - nums[i-1]) * i;
sums.push_back(sum);
}
//找最大对齐状态
int i;
for(i = 0; sums[i] < nums[i+1] && i < n - 1; i++);
i = i - 1;
if(i == -1){
cout << 0 << endl;
return 0;
}
//数学计算
int h, k, N, step;
N = i + 2;
h = sums[i];
k = nums[i+1];
step = (k - h - 1) / (N - 1); //下一步计算h会更新,这里是做个备份
h = h + (k - h - 1) / (N - 1) * N;
if(h < k + step - 1){
h = k + step - 1;
}
cout << h << endl;
return 0;
}
请看题目
Description
chd有 n 个 npy (然鹅 npy 们互相不知情),每个小时 chd 都可以重新选择她接下来这个小时要疼爱的 npy。但是每个 npy 都有自己的怒气上限 ai (1⩽i⩽n),初始所有 npy 怒气都为 0 且每过 1 个小时, 没有被 chd宠幸的人怒气值会加1。一旦某个 npy 的怒气值 达到 自己的怒气上限时他就会爆发, 去找 chd 对峙(或许zjzc??)
问:如果 chd 有选择性的陪他们, 那她最多还能活多久(小时)?
Input
第一行为一个自然数 n,表示 chd 有 n 个 npy
第二行总共 n 个自然数, 第 i 个数 a i 表示 chd 第 i 个 npy 的怒气上限值
Output
一个整数,表示 chd 的最长存活时间
注意:如果 chd 运气好 可以一直存活下去,请输出 “INF”(不含引号)
Hint
数据规模与约定:
n 为不超过 {10}^6106 的自然数(即
0
≤
n
≤
10
6
0 \leq n \leq {10}^6
0≤n≤106 ),
a
i
a_i
ai 为不超过
10
9
{10}^9
109 的自然数
样例说明:
chd 有两个怒气值上限都为 4 的 npy, 首先 chd 花 3 小时疼爱第一个 npy,现在两个 npy 的怒气值
b
1
=
0
,
b
2
=
3
b_1=0,b_2=3
b1=0,b2=3 接下来的 3 个小时 chd宠幸第二个 npy 现在
b
1
=
b
2
=
3
b_1 = b_2 = 3
b1=b2=3 接下来的第 7 个小时,不管 chd 选择哪个 npy 另外一个 npy 一定会跑过去鲨了她,所以第 7 个小时必死无疑,因此答案为 6
完
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/114770.html