2613번 숫자구슬

https://www.acmicpc.net/problem/2613

굉장히 코드가 더럽다..

푼 후에 정리를 못 했다.

다음에 다시 풀어보면서 정리해야할 것.

핵심은 우선 mid를 구하면서 temp vector에 인덱스를 넣는다.(sum과 mid를 고려하면서)

그리고 27번째 줄을 고려해야한다. 

마지막에는 무조건 인덱스가 들어가야한다.

그리고 ans vector도 갱신해주고

86 ~ 89번 째 줄처럼 계산해준다.

ans2의 size가 m보다 작다면 뒤에서부터 1 초과인 숫자들을 1씩 감소시켜주면서 push_back(1)을 해준다.

그룹을 추가시키기 위함.

#include<bits/stdc++.h>
 
using namespace std;
 
int n, m;
vector<int> v, ans, temp;
 
int calc(int s, int e)
{
    return 0;
}
 
bool chk(int mid)
{
    int sum = 0, gc = 1;
    temp.clear();
 
    for (int i = 0; i < v.size(); i++) {
        sum += v[i];
 
        if (sum > mid) {
            ++gc;
            sum = v[i];
            temp.push_back(i - 1);
        }
 
        if (i == v.size() - 1) {
            temp.push_back(i);
        }
 
        if (gc > m || v[i] > mid) {
            return false;
        }
    }
 
    return true;
}
 
int ps(int Left, int Right)
{
    int ret = 2e9;
 
    while (Left <= Right)
    {
        int mid = (Left + Right) / 2;
 
        if (chk(mid)) {
            if (ret > mid) {
                ret = mid;
                ans = temp;
            }
            Right = mid - 1;
        }
        else {
            Left = mid + 1;
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    
    scanf("%d %d", &n, &m);
 
    int sum = 0;
    v.assign(n, 0);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        sum += v[i];
    }
 
    if (m == 1) {
        printf("%d\n%d\n", sum, n);
        return 0;
    }
 
    printf("%d\n", ps(0, sum));
 
    vector<int> ans2;
 
 
    int before = 0;
    for (auto i : ans) {
        ans2.push_back(i + 1 - before);
        before = i + 1;
    }
 
    int as2 = ans.size();
 
    if (as2 < m) {
        for (int i = as2 - 1; i >= 0; i--) {
            while (ans2[i] > 1 && ans2.size() < m)
            {
                --ans2[i];
                ans2.push_back(1);
            }
 
            if (ans2.size() == m) {
                break;
            }
        }
    }
 
    for (auto i : ans2) {
        printf("%d ", i);
    }
 
    printf("\n");
 
    return 0;
}