首页 > 其他分享 >AcWing 4366. 上课睡觉

AcWing 4366. 上课睡觉

时间:2023-01-06 20:23:16浏览次数:67  
标签:上课 4366 int sum 石子 枚举 端点 区间 AcWing

AcWing 4366. 上课睡觉

好久没写题,一写就发现脑子生锈了(。

题目描述

有 \(N\) 堆石子,每堆的石子数量分别为 \(a_1,a_2,⋯,a_N\)。

你可以对石子堆进行合并操作,将两个相邻的石子堆合并为一个石子堆,例如,如果 \(a=[1,2,3,4,5]\),合并第 \(2,3\) 堆石子,则石子堆集合变为 \(a=[1,5,4,5]\)。

我们希望通过尽可能少的操作,使得石子堆集合中的每堆石子的数量都相同。

请你输出所需的最少操作次数。

本题一定有解,因为可以将所有石子堆合并为一堆。

题意

这道题我初步的理解是,要划分出若干个区间,其中每个区间都是连续的,并且每个区间的石子数量和相等,求最小的合并次数,也就是最多的区间数量。

大佬的翻译是这样的:

给你一个长度为 \(n\) 的数组 \(a\),相邻的两个元素可以合并成一个元素。设合并完每个元素都相等的数组 \(a′\) 长度为 \(n′\),求 \(\min \{n−n′\}\)。

解题思路

我一上来想到的就是暴力枚举,但是我的暴力比大佬们的要更简陋,因为缺少了进一步挖掘题意,并且没有根据数据范围作进一步的思考。

我的思路:

  • 从左到右枚举。

  • 首先枚举第一个区间,即固定第一个元素为左端点,枚举其右端点,之后即可每个区间的和\(S\),即每堆石子的个数。

  • 上述右端点右边的元素即第二个区间的左端点,此时继续枚举,目的是找到合法右端点,使得区间和为\(S\)。

    • 若找到,则依次类推继续第三个等;
    • 若未找到,则更改第一个区间的右端点。

    (由于元素非负,则这个区间和递增,若后续区间和达不到这个值,则可认为找不到)

  • 处理特殊情况。。。

  • 时间复杂度应该是O(N_2)

由于数据范围是\(10^5\),因此复杂度大概是\(\text{O}(n\log n)\),也就是说我的做法需要将一个维度优化至\(\log n\)。(也许可能得推翻重来)

优化的思路:

根据题意,由于合并之后每堆石子的个数都相同,设堆数为\(cnt\),则每堆的石子数则为\(S = \frac{sum}{cnt}\)。这个式子说明,\(S\) 是 \(sum\) 的因数。也就是说,没有必要以\(O(n)\)的复杂度枚举第一个区间的右端点来得到\(S\),而是枚举 \(sum\) 的因数,或者说用这个性质作为条件进行优化。具体如下:

  • 从左到右枚举
  • 枚举\(S\),可以是从\(1\)到\(n\),也可以像上面那个思路那样枚举右端点再计算
    • 判断\(S\)是否为\(sum\)的因数,否,则继续枚举
    • 依次判断能否合并为区间和为\(S\)的区间,直到最后
  • 在过程当中统计一下合并次数
  • 特殊情况

代码

// Problem: 上课睡觉
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4369/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;
int T, n;
int a[N], s[N];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    
    cin >> T;
    while(T -- ) {
        cin >> n;
        for (int i = 1; i <= n; i ++ ) {
            cin >> a[i];
            s[i] = s[i - 1] + a[i];
        }
        
        int ans = 0, flag = 0, tepAns = 0;
        for (int i = 1; i <= n; i ++ ) {
            int sum = s[i] - s[0];
            if (sum && s[n] % sum) continue;     // 优化:sum 是所有石子数量之和的因数
            tepAns = i - 1;    // 第一堆石子的合并次数
            
            int left = i + 1;
            for (int right = left; right <= n; right ++ ) {
                int tepSum = s[right] - s[left - 1];    
                if (tepSum == sum) {            // 判断后续区间石子和是否等于 sum
                    if (right != left) tepAns += right - left;// 只有一个元素的区间不需要合并
                    left = right + 1;
                    right = left - 1;
                    continue;
                }
                if (tepSum > sum) {                // 小优化,由于tepSum单增,大于sum就可以结束
                    break;
                }
            }
            
            if (left == n + 1) {
                ans = tepAns;
                break;
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}

标签:上课,4366,int,sum,石子,枚举,端点,区间,AcWing
From: https://www.cnblogs.com/tsrigo/p/17031516.html

相关文章

  • AcWing.1175 最大半连通子图
    题目描述\(\qquad\)一个有向图\(G=(V,E)\)称为半连通的,如果满足:\(\forallu,v\inV\),满足\(u\tov\)或\(v\tou\),即对于图中任意两点\(u,v\),存在一条\(u\)到......
  • AcWing4655.重新排序
    题目原题链接参考题解AcWing4655.重新排序思路用两个数组,一个数组\(a\)来记录原数组,\(b\)数组来记录每个数字被计算了多少次,题目中给的是$[l,r]$区间内的数字求和,......
  • AcWing1174. 受欢迎的牛
    题目描述每一头牛的愿望就是变成一头最受欢迎的牛。现在有\(N\)头牛,编号从\(1\)到\(N\),给你\(M\)对整数\((A,B)\),表示牛\(A\)认为牛\(B\)受欢迎。这种关系......
  • AcWing算法提高课:区间DP
    AcWing算法提高课:区间DP两种实现方式循环式一般对于一维的DP问题可以应用。for(len=1;len<=n;len++)for(l=1;l+len-1<=n;l++)r=l+len......
  • 「AcWing学习记录」区间问题
    AcWing905.区间选点原题链接给定N个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点......
  • acwing4644. 求和
    题目原题链接参考题解方法1思路求两两相乘的和,求a[i]与每个a[j]的乘积的和,就是求a[j]的和与a[i]的乘积所有先把所有数求和sum,然后让\(a[i]*(sum-a[i])\),枚举每一个......
  • Parity Game(奇偶游戏)(POJ1733、AcWing 239)(并查集)(扩展域写法+边带权写法)
    题目小A和小B在玩一个游戏。首先,小A写了一个由0和1组成的序列S,长度为N。然后,小B向小A提出了M个问题。在每个问题中,小B指定两个数l和r,小A回答S[l......
  • AcWing1172. 祖孙询问
    题目描述给定一棵包含\(n\)个节点的有根无向树,节点编号互不相同,但不一定是\(1\simn\)。有\(m\)个询问,每个询问给出了一对节点的编号\(x\)和\(y\),询问\(x\)与......
  • AcWing1170. 排队布局[USACO05]
    解题思路\(\qquad\)这题也是一个比较裸的差分约束:多了的那个输出\(-2\)的其实就是在差分约束系统中\(1\)号点和\(n\)号点没有约束关系,也就是\(1\)和\(n\)号不连通。由于这......
  • acwing.1205 买不到的数目
    acwing.1205买不到的数目小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候,他就用这两种包装来组合。......