The Good Array
题面翻译
题目描述
对于一个由 \(0\) 和 \(1\) 构成的数组 \(a_1,a_2,\dots,a_n\)，如果对于从 \(1\) 到 \(n\) 中所有的整数 \(i\) 都满足以下两个条件，我们称这个数组为『好的数组』：
- 前 \(i\) 个元素中有至少 \(\left\lceil\frac{i}{k}\right\rceil\) 个元素为 \(1\)；
- 后 \(i\) 个元素中有至少 \(\left\lceil\frac{i}{k}\right\rceil\) 个元素为 \(1\)。
其中，\(\left\lceil\frac{i}{k}\right\rceil\) 表示 \(i\) 除以 \(k\) 向上取整。
构造一个长度为 \(n\) 的『好的数组』，使其中 \(1\) 的数量尽可能的少。
输入格式
本题多测。第一行为一个整数 \(t\left(1\le t\le10^4\right)\)，表示有 \(t\) 组数据。
接下来每组样例为一行，包含两个整数 \(n,k\left(2\le n\le100,1\le k\le n\right)\)，题目描述中已经给出。
输出格式
每组样例输出一行一个整数，表示你构造的『好的数组』中 \(1\) 的数量。
题目描述
You are given two integers $ n $ and $ k $ .
An array $ a_1, a_2, \ldots, a_n $ of length $ n $ , consisting of zeroes and ones is good if for all integers $ i $ from $ 1 $ to $ n $ both of the following conditions are satisfied:
- at least $ \lceil \frac{i}{k} \rceil $ of the first $ i $ elements of $ a $ are equal to $ 1 $ ,
- at least $ \lceil \frac{i}{k} \rceil $ of the last $ i $ elements of $ a $ are equal to $ 1 $ .
Here, $ \lceil \frac{i}{k} \rceil $ denotes the result of division of $ i $ by $ k $ , rounded up. For example, $ \lceil \frac{6}{3} \rceil = 2 $ , $ \lceil \frac{11}{5} \rceil = \lceil 2.2 \rceil = 3 $ and $ \lceil \frac{7}{4} \rceil = \lceil 1.75 \rceil = 2 $ .
Find the minimum possible number of ones in a good array.
输入格式
Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.
The only line of each test case contains two integers $ n $ , $ k $ ( $ 2 \le n \le 100 $ , $ 1 \le k \le n $ ) — the length of array and parameter $ k $ from the statement.
输出格式
For each test case output one integer — the minimum possible number of ones in a good array.
It can be shown that under the given constraints at least one good array always exists.
样例 #1
样例输入 #1
7
3 2
5 2
9 3
7 1
10 4
9 5
8 8
样例输出 #1
2
3
4
7
4
3
2
分析
我们先只考虑前i个数字, 在1到k这一段, 我们需要1个1, 从k+1到2k这一段, 我们需要2个1..., 为了使每一段都合法, 那我们肯定要把1放在每一段的开头, 具体来说就是位置1放1, 位置k+1放1, 位置2k+1放1...
因为给的n很小, 我们完全可以先只按以上原则构造, 然后再从后往前遍历, 如果到一个位置发现1不够, 就在那个位置补1个就好了, 时间复杂度为 \(O(n)\)
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int a[N];
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while(t--)
{
memset(a, 0, sizeof a); //多例要清空
int n, k; cin >> n >> k;
int sum = 0; //记录目前放了几个1
for(int i = 1; i <= n; i += k)
a[i] = 1, sum++;
int num = 0;
for(int i = 1; i <= n; i++) //从后往前遍历
{
num += a[n - i + 1]; //记录到目前位置一共有几个1
int cod = (i % k > 0) + i / k; //至少需要cod个1才合法
if(num < cod) sum++, num++; //在这个位置补1个1, num也要更新
}
cout << sum << endl;
}
}