练习赛校园活动题解

//解题核心思路是尺取法
//不过很容易在熟练度为0的人身上被卡点，所以在尺取的时候要把握好尺取结束的条件。
//因为输入的数字之间没有空格，所以可以用字符串来输入再将其转换到数组之中。
// 因为公平要所有的小组的组员的熟练度之和要相等，而我们总共只有n个人，所以最多可以分为n组最少2组，因为熟练度相等，所以我们可以让熟练度之和除以组数，如果能整出在进行尺取判断能否分队成功；
#include<iostream>
#include<string.h>
using namespace std;
#define N 1000006
char op[100000];
int a[N]={0},n;//n为人数，设为全局变量方便在函数中使用；
int check1(int i){ //函数用尺取法来检验能否分组成功并计算分多少组
int l=0,r=0,tt=0,cnt=0;//l为左端点，r为右端点
while(l<n){
while(r<=n&&tt<=i){//因为我们需要考虑到熟练度为0的人，例如4 1010那么我们是需要把最后一个0计入的，所以tt是<=i，i就是传进来的count既每个小组的成员熟练度之和
tt+=a[r];//只有当tt>平均时或右端点到头了才会跳出
r++;
}
if(tt-a[r-1]==i){//因为每组的熟练度得和i相等所以我们跳出循环时是多加了一项的，如果减去这一项就与i相等那么这一组就是分组成功的，只要不相等不管大于小于就都不能完成分组，直接return 0表示分组失败
r=r-1;//r是多加了一次的，所以我们得减去1他的位置才对
l=r;
cnt++;//分组成功了一组cnt就++，cnt就表示分了几组；
tt=0;//tt初始化
}else
return 0;
}
return cnt;
}
int main(){
int sum=0;
cin>>n;
getchar();
cin>>op;
for(int i=0;i<n;i++){//将字符转换成整数存在数组中；
a[i]=op[i]-'0';
sum+=a[i];
}
if(sum==0){//和为0的时候，就是所有人的
cout<<n<<endl;
return 0;
}
int count,flag=0;
for(int i=n;i>1;i--){//最多n组最少2组；
if(sum%i==0){
count =sum/i;//count表示为每一组的熟练度之和 ；
if(check1(count)!=0){//将熟练度带入函数，尺取判断；
cout<<check1(count)<<endl;//因为第一个循环是从n到2所以只要满足的那么就是最多的分组；
flag=1;//输出了标记，方便最后的时候进行判断如果不能分组就输出-1；
break;//输出已经为最优解，所以可以直接跳出；
}
}
}
if(flag==0)cout<<-1<<endl;
return 0;
} </iostream>