Using binary search to find the minimum value,
|
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <string.h> #include <vector> #define ll long long using namespace std; ll b[505]; vector<int> res[505]; int main() { int t; int books,writer; cin>>t; while(t--) { cin>>books>>writer; ll total=0,minwrk=0,mid=0; for(int i=0;i<books;i++) { cin>>b[i]; total+=b[i]; if(minwrk<b[i]) minwrk = b[i]; } //bin search while(minwrk<total) { int required=1; ll sum=0; mid= (total+minwrk)/2; for(int i=0;i<books;i++) { if(sum+b[i]>mid) { required++; sum=0; } sum+=b[i]; } if(required>writer) minwrk=mid+1; else total=mid; } ll sum =0; int j=writer-1; for(int i=books-1;i>=0;i--) { if((sum+b[i])>total || j>i) { j--; sum=0; } sum+=b[i]; res[j].push_back(b[i]); } for(int i=0;i<writer;i++) { for(int l=res[i].size()-1;l>=0;l--) { if(l!=res[i].size()-1) cout<<" "<<res[i][l]; else cout<<res[i][l]; } res[i].clear(); if(i!=writer-1) cout<<" / "; } cout<<"\n"; } return 0; } |