xtu oj 分段

回顾

• 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;
}