Solution UVA: 714 - Copying Books

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss714 - Copying Books	Accepted	C++11	0.000	0.000	1359	3 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	26 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	45 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	54 mins ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	1 hours ago
| discuss714 - Copying Books	Wrong answer	C++11	-	0.000	-	1 hours ago

Suggest:

- max_page is mid of binary_search

- Binary search to find max_page of scribers, when you have max_page you should greedy from right to left (book n -> 1) to get /

- Greedy right to left because they said: "If there is more than one solution, print the one that minimizes the work assigned to the first scriber, then to the second scriber etc. But each scriber must be assigned at least one book."

#include<bits/stdc++.h>

#define int long long

using namespace std;

int a[1000111];

int b[1000111];

int R, L;

vector<int> q, res;

   

void f(int n, int k){

    k -= 1;

    res.clear();

    int l = L, r = R;

   

    while(r - l + 1 >= 3){

       

        int m = (r+l) / 2;

       

        q.clear();

        int s = 0;

        int i = n;

        for(i; i>=1; i--){

            if (s + a[i] <= m){

                s += a[i];

            }  

            else{

                q.push_back(i);    

                s = a[i];

                if (s > m || q.size()==k) break;

            }

                int remain = k - q.size(); //for output 2

                if (remain == i - 1){

                    for(int j= i-1; j>0; j--)

                        q.push_back(j);

                   

                    i = 0;

                    break;

                }

            }

           

        s = 0;

        for(int j=1; j<=i; j++)

            s += a[j];

           

        if (s > m || q.size() > k){

            l = m;

        }

        else if(q.size() < k){

            r = m;

        }  

        else if (q.size() == k){

            r = m;

            res = q;

        }

    }

    int page=-1;

    for(int m= r; m>= l; m--){

        q.clear();

        int s = 0;

        int i = n;

        for(i; i>=1; i--){

            if (s + a[i] <= m){

                s += a[i];

            }  

            else{

                if (i != n) q.push_back(i);    

                s = a[i];

                if (s > m || q.size()==k) break;

            }

           

       

            int remain = k - q.size(); //for output 2

               

                if (remain == i - 1){

                    for(int j= i-1; j>0; j--)

                        q.push_back(j);

                   

                    i = 0;

                    break;

                }

        }

           

        s = 0;

        for(int j=1; j<=i; j++)

            s += a[j];

           

    if (s <= m && q.size() == k){

            page = m;

            res = q;

        }

    }

    for(auto x:res) b[x]= true;

   

}

int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

   

    int t;  cin >> t;

    while(t--){

        R = 1e18, L= -1e18;

        int n, k; cin >> n >> k;

        for(int i=1; i<=n; i++)

            cin >> a[i], b[i]=false, L=max(L, a[i]);

       

        f(n, k);

       

        for(int i=1; i<=n; i++)

            cout<<a[i]<<(i==n? "" : (b[i] ? " / " : " "));

        cout<<"\n";

    }

}