校acm新生赛笔记

导读:本篇文章讲解 校acm新生赛笔记,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com


题目链接: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+(kh1)/(N1)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+Nx+1
可计算机并不擅长解方程,它比较喜欢计算表达式。但问题不大,我们只需将方程变形一下:

h

=

h

+

(

k

h

1

)

/

(

N

1

)

N

h=h+(k-h-1)/(N-1)*N

h=h+(kh1)/(N1)N
但这还不够,通过该表达式计算出来的只是表格第四行的h = 10。我们可以观察到,此时数组元素的值为12,而最大操作次数正是

12

1

=

11

12-1=11

121=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⩽in),初始所有 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

0n106 ),

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

(0)
Java光头强的头像Java光头强

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!