标签：10 check return int sum Sleeping 枚举 USACO22FEB Class

好题分享——[USACO22FEB] Sleeping in Class B

洛谷题目链接

题面翻译

\(T\) 组数据，每组给定一个长度为 \(N\) 的数组 \(a_1, a_2, \dotsb , a_n\)。

每次操作可选择两个相邻的数合并，得到的新数为两者之和。

求最少操作次数使得所有数相等。

数据范围： \(1 \leq T \leq 10\)，\(\sum a_i \leq 10^6\)，\(\sum N \leq 10^5\)，\(1 \le T \le 10\)。

【输入格式】

一行一个整数 \(T\)。

接下来 \(T\) 组数据，每组数据第一行一个整数 \(N\)，第二行 \(N\) 个整数，\(a_1, a_2, \dotsb , a_n\)，含义如题目描述。

【输出格式】

\(T\) 行，每行一个整数，表示最少操作次数。可证明总存在一种操作满足题意。

【样例解释】

对于样例 \(1\)，显然可以通过如下 \(3\) 次操作将原序列变成 3 3 3：

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

对于样例 \(2\)，显然可以通过如下 \(2\) 次操作将原序列变成 7：

   2 2 3
-> 2 5
-> 7

对于样例 \(3\)，显然无需操作。

首先，对于10^5的数量级，只需考虑O(n)或O(nlogn)的算法

考虑到这道题每个合并起来的堆的元素个数是不确定的，状态转移也没有确定的规律

所以基本可以确定，不能用O(n)的DP做法解决

那么，就考虑nlogn数量级的方法

但这道题跟logn有什么关系呢？

我想了半天，并没有发现什么（这题跟二分似乎也没关系）。

那干脆就先打个n^2的暴力算法再说吧！

我们枚举最后的堆数，

堆数越多意味着合并次数越少，那么从大到小枚举，

第一个找到的可行解就是最优解

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
bool check(int x, int n)//x为每堆的总和 
{
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum += a[i];
		if(sum > x) return false;
		if(sum == x) sum=0;
	}
	return true;
} 
inline void solve()
{
    int n, sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i], sum+=a[i]; 
    if(sum==0)//特殊情况，特判一下 
    {
        cout<<0<<endl;
        return;
    }
    for(int i=n;i>=1;i--)
    	if(sum%i==0 && check(sum/i, n)) //如果能均分，就check一下
		{
			printf("%d\n", n-i);//合并为i堆，那么要合并n-i次	
			return;
		} 
    return;
} 
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

if(sum%i==0 && check(sum/i, n))

这是个很容易想到的优化策略，不能均分就没必要check

当我们写到这句时，其实就会发现打暴力不能算O(n^2)

因为一个数的因子个数是很少的

这里补充两个小知识点：

①设\(f(n)\)=n的因子个数，我们可以认为\(f(n)\)和logn是一个数量级的。

②对于C++的if语句来说，&&连接的判断条件不是并行判断的，而是按顺序判断，第一个bool若为false，就不在执行之后的语句。

好了，这样我们就AC了这道题

不过事实上，我还想到了另一种枚举的思路，感觉上可以优化一下常数

先放代码再解释

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int sum[N];
inline void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i], sum[i]=sum[i-1]+a[i];
    if(sum[n]==0)
    {
        cout<<0<<endl;
        return;
    }
    for(int i=1; i<=n; i++)
    {
        bool flag=true;
        int k=sum[i];
        int s=0;
        if(k==0) continue;
        if(sum[n]%k != 0) continue;
        for(int j=i+1; j<=n; j++)
        {
            s+=a[j];
            if(s > k)
            {
                flag = false;
                break;
            }
            if(s == k) s=0;
        }
        if(flag)
        {
            cout<<n-sum[n]/k<<endl;
            break;
        }
    }
    return;
} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

以最前面一堆的总数进行枚举

假设第一堆为编号1~i的数，总和为k

那么在这种状态下，之后一定能找到sum/k-1个总和为k的连续子序列

否则就是k不满足题意

而我们不难发现：合并次数最少，就意味着k最小

那么只要i从小到大枚举就可以

OK 这个代码也完美AC ！

更新预告：下一期将分享两道关于异或的题

标签：10,check,return,int,sum,Sleeping,枚举,USACO22FEB,Class
From： https://www.cnblogs.com/zhouzhihao/p/17017969.html

[USACO22FEB] Sleeping in Class B