hihocoder-Weekly224-Split Array
题目1 : Split Array
描述
You are given an sorted integer array A and an integer K. Can you split A into several sub-arrays that each sub-array has exactly K continuous increasing integers.
For example you can split {1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6} into {1, 2, 3}, {1, 2, 3}, {3, 4, 5}, {4, 5, 6}.
输入
The first line contains an integer T denoting the number of test cases. (1 <= T <= 5)
Each test case takes 2 lines. The first line contains an integer N denoting the size of array A and an integer K. (1 <= N <= 50000, 1 <= K <= N)
The second line contains N integers denoting array A. (1 <= Ai <= 100000)
输出
For each test case output YES or NO in a separate line.
- 样例输入
-
2 12 3 1 1 2 2 3 3 3 4 4 5 5 6 12 4 1 1 2 2 3 3 3 4 4 5 5 6
- 样例输出
-
YES NO
题解：
很简单的题目
因为该数组是已经排好序的，而且其范围是1-10^6 , 可以用一个数组记录每一个数的cnt，然后顺序便利一遍，就可以判断。
时间复杂度： O(10^6)
#include <cstdio>
#include <cstring>
#include <cstdlib>
const int MAXN = 100000 + 10;
#define max(a, b) (a)>(b)?(a):(b)
#define min(a, b) (a)>(b)?(b):(a)
int n, k, num[MAXN];
int main(){
int test_case;
scanf("%d", &test_case);
int x, min_x, max_x, tmp;
bool ans;
while(test_case--)
{
memset(num, 0, sizeof(num));
scanf("%d %d", &n, &k);
max_x = 0; min_x = MAXN;
for(int i=0; i<n; ++i)
{
scanf("%d", &x);
num[x]++;
max_x = max(max_x, x);
min_x = min(min_x, x);
}
if(n%k != 0){
printf("NO
");
continue;
}
ans = true;
for(int i=min_x; i<=max_x; ++i)
{
if(num[i] > 0)
{
tmp = num[i];
for(int j=0; j<k; ++j)
{
if(i+j > max_x){
ans = false;
break;
}
num[i+j] -= tmp;
}
}else if(num[i] < 0)
{
ans = false;
break;
}
}
if(ans){
printf("YES
");
}else{
printf("NO
");
}
}
}