Algoogle

Algorithm for Programming Contest

PKU 3273 Monthly Expense

Category: PKU Tag: binary-search

Monthly Expense

問題概要


解法


分割した時の各セクションの出費の最大値を2分探索する

コード


(3273.cpp) download
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
#include <iostream>
#include <vector>
#define rep(i,a) for(int i = 0;i < (a); i++)
using namespace std;
typedef vector<int> vi;

int N, M;
vi spends;

bool can(int n){
    int cnt = 0, sum = 0;
    rep(i,N){
        if(sum + spends[i] > n){
            sum = 0;
            cnt++;
        }
        sum += spends[i];
        if(sum > n) return false;
    }
    return cnt < M;
}

int main(){
    cin >> N >> M;
    spends.resize(N);
    rep(i,N) cin >> spends[i];
    int lb = 0, ub = 1000000100;
    while(lb + 1 < ub){
        int mid = (lb + ub) / 2;
        if(can(mid)) ub = mid;
        else lb = mid;
    }
    cout << ub << endl;
    return 0;
}

Comments