xtu oj 分段
文章目录
- 回顾
- 思路
- C 语言代码
回顾
- A+B III
- 问题 H: 三角数
- 问题 G: 3个数
- 等式 数组下标查询,降低时间复杂度
- 1405 问题 E: 世界杯
- xtu 数码串
- xtu oj 神经网络
- xtu oj 1167 逆序数(大数据)
- xtu oj 原根
- xtu oj 不定方程的正整数解
- xtu oj 最多的可变换字符串
- xtu oj String I
- xtu oj 字母序列
思路
这题有一个需要考虑的细节,就是我们给因子个数开多大的存储空间,假设数字的上限是 10^9
,那么我们用一个 150
的数组空间存因子个数是否足够呢?其实是不够的。把一个数字做质因数分解,然后把幂指数加一做连乘,就是因子个数。这里具体是多大我也不知道,反正稍微多写几个零比较保险,但是别写太多。三四个零应该差不多。可能大几百也可以。
从样例出发,去思考这个问题,有点从特殊到一般的那种感觉。1 2 3 1 2 3
,可以分成多少段,不要求均分,但是我们也不可以把一个完整的数字分成几个部分,比如不能把 2
分成 1
和 1
,我们只能按照其原本的顺序去分。 总共 6
个数字,要求分成的段的和相等,那我们把总和 sum
分解,找出它的所有因子,这个因子有两种理解方式。
第一种是理解为段数,比如说样例的 sum==12
,段数可以是 12
的因子,1,2,3,4,6,12
,但是 12
大于数字个数 n==6
,所以要舍弃,也就是说有五种分法,我们从最大的段数开始分,找到符合条件的输出答案结束循环即可。因为段数越大,每一段的和就越小。
第二种是理解为每一段的和。我们知道,每一段的和*段数=sum
,段数和每一段的和都是 sum
的因子,这就是我们有两种理解方式的原因。第二种就更加直观。直接从最小的每一段的和开始遍历,找到符合条件的就结束就行了。下面的代码也是从这个思路展开的。
其他细节都写在注释里面了。
C 语言代码
#include<stdio.h>
#include<stdbool.h>
//存输入的数字
int a[100010];
//存因子,稍微开大点儿
int b[10000];
int main(){
int n;
scanf("%d",&n);
//sum 表示整个的和
int sum=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
//把 sum 的因子作为每一段的和存进 b 数组
int cnt=0;
//这里用 i*i 后面还要排序,不是多此一举,是因为 sum 是 10^9 ,假设遍历一遍就超时了,i*i 这样写就是根号的时间复杂度。
for(int i=1;i*i<=sum;i++){
if(sum%i==0){
b[cnt++]=i;
if(sum/i!=i){
b[cnt++]=sum/i;
}
}
}
//从小到大排序
//注意总共是有 cnt+1 个元素,b[cnt]里面也是有元素的。
//冒泡排序一直有点记不住,现在再记一下,第一层循环是 n-1 ,第二层循环是 n-1-i 比较的是 arr[j] 和 arr[j+1]
for(int i=0;i<cnt;i++){
for(int j=0;j<cnt-i;j++){
if(b[j]>b[j+1]){
int temp=b[j];
b[j]=b[j+1];
b[j+1]=temp;
}
}
}
//注意有 cnt+1 个数字
for(int i=0;i<=cnt;i++){
//求每一小段的和
int sum1=0;
//true 表示找到答案
bool flag=true;
for(int j=0;j<n;j++){
sum1+=a[j];
//表示这一小段可以达到 b[i] 这个要求的和,我们就是判断一小段的和能不能达到我们预期的和,这个和是我们所有和 sum 的因子
if(sum1==b[i]){
sum1=0;
}else if(sum1>b[i]){
//假设我们加着加着超过了,那就不能满足要求,这里可以仔细考虑是不是这个情况
flag=false;
break;
}else{
//小于,就继续加
continue;
}
}
//输出预期的最小的和,并跳出循环
if(flag){
printf("%d\n",b[i]);
break;
}
}
return 0;
}