收入计划

Algorithms
二分, 贪心

问题描述

高考结束后，同学们大都找到了一份临时工作，渴望挣得一些零用钱。从今天起，Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干天里没有领取的工资，但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱，他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次，且需要将所有的工资全部领走（即最后一天末需要领一次工资）。

输入

第一行输入两个用空格隔开的正整数N和M
以下N行每行一个不超过10000正整数，依次表示每一天的薪水。

输出

输出领取到的工资的最大值最小是多少。

样例输入

1
2
3
4
5
6
7
8
7 5
100
400
300
100
500
101
400

样例输出

1
500

样例说明

采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了。
100 400 300 100 500 101 400 每一天的薪水
<——1 <——-2 <—3 <—4 <—5 领取工资的时间
500 400 500 101 400 领取到的工资

分析

最小值最大/最大值最小类问题 -> 二分答案典型问题

二分答案模板，对于 l 与 r 的理解，不要仅仅用「二分法解方程」的思想理解，此类题 可把 l 看作不可行域， r 看作可行域 。

此题需要二分工资最大值（单次领取的最高工资必定在 [单日工资最大值,全部工资] 的区间内）利用贪心（从左到右能取就取），判断是否可行。

二分答案模板

1
2
3
4
5
6
7
8
9
10
while(l<=r)
{
	int mid=(l+r)>>1;
	if(check(mid))
	{
		ans=mid;
		r=mid-1;
	}
	else l=mid+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
# include<iostream>
using namespace std;
int n,m,sum=0,maximum=-1,ans;
int a[101000];
int check(int x)
{
	int i;
	int times=0,tot=0;
	for(i=1;i<=n;i++)
	{
		tot=tot+a[i];
		if(tot>x)
		{
			tot=a[i];
			times++;
		}
		if(times+1>m)//判断是否恰好领 m 次，注意是 times+1
			return 0;
	}
	return 1;
}
int main()
{
	int i;
	cin >>n>>m;
	for(i=1;i<=n;i++)
	{
		cin >>a[i];
		maximum=max(maximum,a[i]);
		sum=sum+a[i];
	}
	int l=maximum,r=sum;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout <<ans<<endl;
	return 0;
}
分享到