핵심 아이디어

<aside> 💡

넣을 수 있는 파의 양에 대해 이분탐색

이후 최대한 파를 넣고 남은 양을 구하기

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int n, m;
int a[1'000'001];

signed main()
{
    FASTIO;
    int mx = 0;
    ll sum = 0;

    cin >> n >> m;
    for(int i = 0; i<n; i++){
        cin >> a[i];
        sum += a[i];
        mx = max(mx, a[i]);
    }

    ll lo = 0, hi = mx+1;
    while(lo+1<hi){
        ll mid = lo+hi>>1;

        ll cnt = 0;
        for(int i = 0; i<n; i++){
            cnt += a[i]/mid;
            if(cnt>=m) break;
        }

        if(cnt>=m) lo = mid;
        else hi = mid;
    }

    cout << sum-lo*m <<"\\n";
    return 0;
}

남은 양을 구할 때 괜히 모듈러를 써서 몇 번 틀렸다.

파를 넣을 수 있는 대로 넣을 수 없기 때문에 모듈러가 정답이 아니다.