POJ3273 Monthly Expense

Posted on | In |

分期：将N个账款分割成M个财务期，使得每个分期账款和的最大值最小。

思路

bool C(int d) = 分解成 M 個區間後，最大的區間和 s <= d
盡量把一個區間的值塞滿，直到塞不下。
也就是說，從左至右迭代 A[i]，如果前一個區間的總和再加上 A[i] 會大於 d 的話，
則 A[i] 就是下個區間的起始點。最後看區間的數量是否 <= M

代码

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
60
61
62
#include<iostream> 
#include <cstring>
#include <algorithm> 
#define ll long long
using namespace std;
ll m,n,d;
int a[100000];
//bool check(int mid){
//	ll cnt=1;
//	int sum=0;
//	for(int i=0;i<n;i++){
//		sum+=a[i];
//		if(sum>mid) {
//			cnt++;
//			sum=a[i];
//		}
//		if(cnt>m) return false;
//	}
//	return true;
//}
bool check(int mid){
	ll cnt=1;
	int sum=0;
	for (int i = 0; i < n; i++)
        if (a[i] > mid)
            return false;
	for(int i=0;i<n;i++){
	
		if(sum+a[i]>mid) {
			cnt++;
			sum=a[i];
		}
		else 	sum+=a[i];
	
	}
	if(cnt>m) return false;
	return true;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){//!!!
		scanf("%d",&a[i]);
	}

//	sort(a,a+n); 不用排序 连续挑选月份 
	int sum=0;
	for(int i=0;i<n;i++)
		sum+=a[i];
	int L,R,ans=0;
	L=0;
	R=sum;
	while(L<=R){
		int mid=(L+R)/2;
		if(check(mid)){
			ans=mid;
			R=mid-1;
		}
		else L=mid+1;
	}
	cout<<ans<<endl;	
	return 0;
}