【每日一题】—— B. Arrays Sum （Grakn Forces 2020）

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

题目大意：

题目链接：

B. Arrays Sum （Grakn Forces 2020）

二.思路分析

这题是一个贪心模拟题
首先ai=b1i+b2i+…+bki；如下图：

所以我们可以尝试每次b的取值都和a相等，一直取到k次，k次之后就不改变b的取值，以此往复。

最后考虑一下特殊情况，就是k为1的时候，如果a数组里的值不是全相等的话，无法实现，因为第一个数肯定是0，如果k为1那么b的值只能是0，后面的值就无法减小。

三.代码展示

//https://codeforces.com/problemset/problem/1408/B
//再k次以内优先选择最优的数
//
#include
#include
#define int long long
using namespace std;

int s[200020];

void solve()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
	}
	//特判
	if(k==1&&s[0]!=s[n-1])
	{
		cout<<"-1"<<"\n";
		return;
	}
	int ans=0;//记录答案
	while(s[n-1]!=0)
	{
		int cur=s[0];
		int count=0;//记录与k的次数
		for(int j=0;j<n;j++)
		{
			if(s[j]==cur)
			{
				s[j]=0;
			}
			else
			{
				if(count!=k)
				{
					cur=s[j];
					count++;
					j--;
					continue;
				}
				else
				{
					for(int i=j;i<n;i++)
					{
						s[i]-=cur;
					}
					break;
				}
			}
		}
		ans++;
	}
	cout<<ans<<"\n";
}

signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

最后：

每日一题系列旨在养成刷题的习惯，所以对代码的解释并不会特别详细，但足够引导大家写出来，选的题目都不会特别难，但也不是特别简单，比较考验大家的基础和应用能力，我希望能够将这个系列一直写下去，也希望大家能够和我一起坚持每天写代码。

之后每个星期都会不定期更新codeforces和atcoder上的题目，想要学习算法的友友们千万别错过了，有什么疑问欢迎大家在评论区留言或者私信博主！

在这里送大家一句话：广积粮，缓称王！