This problem was used for: (@ Top coder) Single Round Match 169 Round 1 – Division I, Level Two Single Round Match 169 Round 1 – Division II, Level Three Problem Link class FairWorkload{ public: int getMostWork(vector<int> folder,int worker) { int n = folder.size(); int lw = *max_element(folder.begin(),folder.end()); int hi = accumulate(folder.begin(),folder.end(),0); int mid_load; int
Category: Binary Search
880
#include <iostream> #include <cstdio> #define ul unsigned long long #define INT_MX 2147483641 using namespace std; ul binsearch(ul n,ul lw,ul hi) { ul mid; ul tmp,tmp1,tmp2; while(lw<hi) { mid=(lw+hi)/2; tmp = (mid*(mid+1))/2; if(tmp<=n) lw=mid+1; else if(tmp>n) hi=mid; } return hi; } int main() { ul n; ul diff,hi,lw; ul neumenator,denominator; while(cin>>n) { hi = binsearch(n,0,INT_MX); diff
10611
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int arr[50005]; int binSearch(int num,int lw,int hi) { int mid; while(lw<hi) { mid = (hi+lw)/2; if(num<arr[mid]) hi = mid; else if(num>=arr[mid]) lw = mid+1; } return hi; } int main() { int N,Q,a; int len,qry,idx; while(scanf("%d",&N)!=EOF) { scanf("%d",&arr[0]); len = 1; for(int i=1;i<N;i++) { scanf("%d",&a); if(a!=arr[len-1])
10487
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <iostream> //#include <cstdlib> #define ll long long using namespace std; int a[1010]; vector<int> sum; int binarySearch(int num,int lw,int hi) { if(hi-lw==1) { int diff1 = abs(num-sum[lw]); int diff2 = abs(num-sum[hi]); if(diff1<diff2) return sum[lw]; else return sum[hi]; } int mid=(lw+hi)>>1; if(num<=sum[mid]) return binarySearch(num,lw,mid); else return binarySearch(num,mid,hi); return
714
Using binary search to find the minimum value, #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