求问站外题

灌水区

Dream__Sky @ 2023-05-08 23:20:17

题目描述

小明的数学计算能力超强，常常在同学们面前表面得很骄傲。数学科代表实在看不下去了，决定出道很麻烦的题，好好“折磨”他一下。

数学科代表决定给他一些数，让他分组。从第一个数开始分组，且每组必须是连续的一段数，要求每组和相等，问每组和最小可以是多少。（当然这些数一定可以被分组，大不了直接分成一组。）

输入

第一行为一个数N

第二行为N个整数（每个数均小于等于1000），两个数间用空格隔开。

输出

一行，最小的和

样例输入输出

输入#1

2 5 1 3 3 7

输出#1

输入#2

1 1 2 3 2 3

输出#2

提示

【样例1说明】

分成三组（2，5）（1，3，3）（7）和为7，不存在比7更小的和。

【数据规模】

测试点 n

1	n=10
2	n=100
3	n=1000
4	n=200000
5	n=200000
6	n=1000000
7	n=1000000
8	n=1000000
9	n=1000000
10	n=1000000

这道题正解是什么？

#include<bits/stdc++.h>
using namespace std;
long long s,minsum=1e+15;
int a[1000001],n,i;
bool find(long long I){
    long long cnt=0;
    for(i=1;i<=n;i++){
        cnt+=a[i];
        if(cnt>I)return 0;
        if(cnt==I)cnt=0;
    }
    return 1;
}
int main()
{
    scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);s+=a[i];}
    for(long long i=1;i*i<=s;i++){
        if(find(i))minsum=min(minsum,i);
        if(find(s/i))minsum=min(minsum,s/i);
    }
    cout<<minsum;
}

数据有点水，这个暴力枚举每种可能的答案的代码都能过（还是本来就能过？）

如果本来就能过，能不能说明一下最劣的情况，以及时间复杂度

如果不行，各位大佬能不能提供一下正解的思路

谢谢！

by Fjionzy @ 2023-05-08 23:26:41

@Dream__Sky 二分？

by Fjionzy @ 2023-05-08 23:26:52

@Dream__Sky 我试试

by Charon__ @ 2023-05-08 23:29:24

@StarlitSky 二分答案应该不存在单调性吧。（雾）

by Dream__Sky @ 2023-05-08 23:30:26

那二分答案怎么求最小

by Dream__Sky @ 2023-05-08 23:30:53

@Kasa_ 我也觉得

by Fjionzy @ 2023-05-08 23:31:39

@Kasa_ 我做过类似的，应该是二分

by Fjionzy @ 2023-05-08 23:34:16

@Kasa_ 好像也是

by Fjionzy @ 2023-05-08 23:34:57

@Dream__Sky

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],s;
long long start,finish,mid;
bool pd(long long x)
{
    long long t=0;
    for(int i=1;i<=n;i++)
    {
        t+=a[i];
        if(t==x) t=0;
        else if(t>x) return false;
    }
    if(t==0) return true;
    else return false;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],s+=a[i];
    start=0,finish=s+1;
    while(start+1<finish)
    {
        mid=(start+finish)/2;
        if(pd(mid)) finish=mid;
        else start=mid;
    }
    cout<<finish;
    return 0;
}

by Dream__Sky @ 2023-05-08 23:37:23

@StarlitSky 错了

by Dream__Sky @ 2023-05-08 23:38:09

没有单调性吧，有时候反而有些小的还凑不好，大的就刚刚好了

| 下一页