/* http://usaco.org/index.php?page=viewproblem2&cpid=619 (create a free account) USACO 2016 Feburary Silver Ques. 2: Load Balancing This code is not for Sololearn, I recommend onlinegdb.com or visual studio code 7 7 3 5 5 7 13 3 1 11 7 5 3 9 1 Output: 2 I recommend not copying this code into USACO though it works cause you need to do it yourself. */ #include #include #include #include using namespace std; typedef pair pii; vector cow_pos, cow_pos2; vector x_pos; int n; bool sortbysec(const pair &a, const pair &b) { return (a.second < b.second); } int maximum(int a, int b, int c, int d){ int check[4] = {a, b, c, d}; int result = 0; for(int i = 0; i < 4; i++){ result = result < check[i]? check[i]: result; } return result; } int main(){ ifstream fin("balancing.in"); ofstream fout("balancing.out"); fin >> n; int x = 0; for(int i = 0; i < n; i++){ int a, b; fin >> a >> b; cow_pos.push_back(make_pair(a, b)); cow_pos2.push_back(make_pair(a, b)); } sort(cow_pos.begin(), cow_pos.end()); sort(cow_pos2.begin(), cow_pos2.end(), sortbysec); int indx = 0; for(int i = 0; i < cow_pos[n - 1].first + 1; i++){ if(cow_pos[indx].first == i){ while(cow_pos[indx].first == cow_pos[indx + 1].first){ x++; indx++; } x++; indx++; } x_pos.push_back(x); } int result = INT_MAX; for(int i = 0; i < n - 1; i++){ if(cow_pos[i].first == cow_pos[i + 1].first){ continue; } int vline = cow_pos[i].first + 1; int lu = x_pos[vline]; int ru = x_pos[x_pos.size() - 1] - lu; int ld = 0, rd = 0; int y_start = 0; for(int y = 0; y < n - 1; y++){ int hline = cow_pos2[y].second + 1; for(int yindx = y_start; yindx < n; yindx++){ if (cow_pos2[yindx].second > hline) { int tmp_result = maximum(lu, ld, ru, rd); result = tmp_result < result ? tmp_result : result; y_start = yindx; break; } else if(cow_pos2[yindx].first < vline){ ld++; lu--; // y_start++; } else{ rd++; ru--; // y_start++; } } } } fout << result << endl; fout.close(); fin.close(); return 0; }

USACO #35 Load Balancing (Silver) C++