【CSES】1085. Array Division

題目連結

時間複雜度

• $O(NlogN)$

解題想法

這題是很裸的對答案二分搜題，只要

$O(logN)$ 搜答案，然後

$O(N)$ 去檢查答案就可以過了

完整程式

檢查答案的地方有一個值得注意的地方就是第24行的 if( arr[ind] > ans ) return false; 這個要記得加上去，否則有時候會莫名其妙回傳錯的東西回去，目的是為了避免子集合裡面有超過答案的數字出現

/* Question : CSES 1085. Array Division */

#include<iostream>
#include<iomanip>
#include<vector>
#include<queue>
#include<stack>
#include<math.h>
#include<algorithm>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long

const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;
int n, k, res, op, ind, tmp;
int arr[MAXN];

bool valid( int ans ){
    op = 1, ind = 0, tmp = 0;

    while( ind < n ){
        if( arr[ind] > ans ) return false;
        if( tmp + arr[ind] <= ans ){
            tmp += arr[ind];
        }else{
            op++;
            tmp = arr[ind];
        }
        ind++;
    }

    return op <= k;
}

signed main(){
    opt;
    cin >> n >> k;
    for( int i = 0 ; i < n ; i++ ){
        cin >> arr[i];
    }

    int step = 1e18;
    while( step > 0 ){
        if( !valid( res + step ) ) res += step;
        else step /= 2;
    }

    cout << res+1 << "\n";
}