数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\leq N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。

将其如下分段：

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

样例 #1

样例输入 #1

1
2
5 3
4 2 4 5 1

样例输出 #1

1
6

提示

对于 $20\%$ 的数据，$N\leq 10$。

对于 $40\%$ 的数据，$N\leq 1000$。

对于 $100\%$ 的数据，$1\leq N\leq 10^5$，$M\leq N$，$A_i < 10^8$， 答案不超过 $10^9$。

题解

思路

这道题球的是最大值的最小，所以要用到二分，根据题意，这道题的和最小为数组中的某一个数的最大值，最大为整个数组的和。因此，我们确定二分的范围，让左值的等于数组中的最大值，右值取得整个数组的和。然后我们需要的如何分段，当我们让遍历数组，如果每次相加小于中间值，就接着相加，否则就重开一段，再让变量当计数器去++，这样就有两段了，以此类推。直到变量大于等于段数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

int n, m, a[100005]; // 修改数组大小为100005
int l = 0, r = 0, mid, ans; // 显式初始化左右边界

bool check(int x) {
    int tot = 0, num = 0;
    for (int i = 1; i <= n; i++) {
        if (tot + a[i] <= x) {
            tot += a[i];
        } else {
            tot = a[i];
            num++;
        }
    }
    return num >= m;
}

int main() {
    scanf("%d%d", &n, &m); // 使用scanf进行输入
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        l = max(l, a[i]);
        r += a[i];
    }

    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    
    printf("%d\n", l); // 使用printf进行输出
    return 0;
}


[NOIP2015 提高组] 跳石头

题目背景

NOIP2015 Day2T1

题目描述

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$， 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

样例输出 #1

1
4

提示

输入输出样例 1 说明

将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$（从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。

数据规模与约定

对于 $20\%$的数据，$0 \le M \le N \le 10$。
对于 $50\%$ 的数据，$0 \le M \le N \le 100$。
对于 $100\%$ 的数据，$0 \le M \le N \le 50000,1 \le L
\le 10^9$。

题解

思路

这道题求的是最短距离的最大，因此，我们需要二分，在这里我们将取得中间值与每次数组的前后差值去比较，小于中间值，我们就将其变量tot++，否则让数组的下一个接着减去上一个。直到tot小于移走岩石的数量。然后再二分中让符合结果的答案等于中间值，直到缩短区间后取得的最大中间值即为答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
using namespace std;

int l, n, m;
int a[500010];

bool judge(int x) {
    int tot = 0, now = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (a[i] - a[now] < x)
            tot++;
        else
            now = i;
    }
    return tot <= m;
}

int main() {
    cin >> l >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    a[n + 1] = l;

    int ll = 0, rr = l;
    int ans = 0;
    while (ll <= rr) {
        int mid = ll + (rr - ll) / 2;
        if (judge(mid)) {
            ans = mid;
            ll = mid + 1;
        } else {
            rr = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

书的复制

题目背景

大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出 0 0 。

不过，已经修改数据，保证每个人都有活可干。

题目描述

现在要把 $m$ 本有顺序的书分给 $k$ 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

输入格式

第一行两个整数 $m,k$。

第二行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 本书的页数。

输出格式

共 $k$ 行，每行两个整数，第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。 $k$ 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

样例 #1

样例输入 #1

1
2
9 3
1 2 3 4 5 6 7 8 9

样例输出 #1

1
2
3
1 5
6 7
8 9

提示

$1\le k \le m \le 500$。

题解

思路

这题求得是抄书最多页的人用时最少，既求最大值的最小，因此用到二分答案的思想，然后这道题为了让前面的人少抄，因此就要让后面的人多抄，所以从后往前遍历，所以要倒序遍历。然后将其分成m段，且每段的和不超过最优解s。然后再二分查找，二分的时候最低是数组中最大值，最高为整个数组的和。输出的时候，因为考虑到时倒序输入，因此需要我们倒序输出，输出的时候要终止的下标比起始的下标大1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;

long long n,m;
long long a[502];
int x[502],y[502];

bool check(int s){
	int num=1,t=0;
	for(int i=n;i>=1;i--){
		if(t+a[i]>s)
			t=0,
			num++;
		t+=a[i];
	}
	return num<=m;
}

int find(int low,int high){
	int mid;
	while(low+1<high){
		mid=low+(high-low)/2;
		if(check(mid))
			high=mid;
		else 
			low=mid;
	}
	return high;
}

int main(){
	long long low=0,high=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		high+=a[i];
		low=max(low,a[i]);
	}
	int s=find(low,high);
	int t=0,num=1;
	for(int i=1;i<=m;i++){
		x[i]=y[i]=0;
	}
	y[1]=n;
	for(int i=n;i>=1;i--){
		if(t+a[i]>s){
			t=0;
			x[num]=i+1;
			y[++num]=i;
		}
		t+=a[i];
	}
	x[num]=1;
	
	for(int i=m;i>=1;i--){
		cout<<x[i]<<" "<<y[i]<<endl;
	}
	return 0;
}