#include <bits/stdc++.h> using namespace std; struct road { int length; int infectedAround; int dayToInfect; }; bool compareRoads(road r1, road r2) { double r1Value = ((r1.length*1.0)/r1.infectedAround); double r2Value = ((r2.length*1.0)/r2.infectedAround); return r1Value < r2Value; } int task(int n, string citiesState) { vector<road> roads; int totalInfected = 0; int length = 0; int infectedAround = 0; for(int i = 0; i < n; i++) { if(citiesState[i] == '1') { totalInfected++; if(length > 0) { roads.push_back({ length, infectedAround+1, static_cast<int>(ceil((length*1.0)/(infectedAround+1.0))) }); length = 0; } infectedAround = 1; } else { length++; } } if(length > 0 and infectedAround) { roads.push_back({ length, infectedAround, static_cast<int>(ceil((length*1.0)/(infectedAround)))}); } sort(roads.begin(), roads.end(), compareRoads); int dayCount = 0; int iterator = roads.size() - 1; if(iterator == -1) { return totalInfected; } while(roads[iterator].dayToInfect > dayCount) { totalInfected += dayCount*roads[iterator].infectedAround; if(roads[iterator].infectedAround == 2) { int updatedLength = roads[iterator].length - dayCount*roads[iterator].infectedAround; dayCount += 2; if(updatedLength > 1) totalInfected++; if(updatedLength == 2) dayCount--; } else { dayCount += 1; } iterator--; } for(int i = 0; i <= iterator; i++) { totalInfected += roads[i].length; } return totalInfected; } int main() { std::ios_base::sync_with_stdio(false); int t; cin >> t; for(int i = 0; i < t; i++) { int n; string citiesState; cin >> n; cin >> citiesState; cout<<task(n, citiesState)<<endl; } return 0; }
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 84 85 86 87 88 89 | #include <bits/stdc++.h> using namespace std; struct road { int length; int infectedAround; int dayToInfect; }; bool compareRoads(road r1, road r2) { double r1Value = ((r1.length*1.0)/r1.infectedAround); double r2Value = ((r2.length*1.0)/r2.infectedAround); return r1Value < r2Value; } int task(int n, string citiesState) { vector<road> roads; int totalInfected = 0; int length = 0; int infectedAround = 0; for(int i = 0; i < n; i++) { if(citiesState[i] == '1') { totalInfected++; if(length > 0) { roads.push_back({ length, infectedAround+1, static_cast<int>(ceil((length*1.0)/(infectedAround+1.0))) }); length = 0; } infectedAround = 1; } else { length++; } } if(length > 0 and infectedAround) { roads.push_back({ length, infectedAround, static_cast<int>(ceil((length*1.0)/(infectedAround)))}); } sort(roads.begin(), roads.end(), compareRoads); int dayCount = 0; int iterator = roads.size() - 1; if(iterator == -1) { return totalInfected; } while(roads[iterator].dayToInfect > dayCount) { totalInfected += dayCount*roads[iterator].infectedAround; if(roads[iterator].infectedAround == 2) { int updatedLength = roads[iterator].length - dayCount*roads[iterator].infectedAround; dayCount += 2; if(updatedLength > 1) totalInfected++; if(updatedLength == 2) dayCount--; } else { dayCount += 1; } iterator--; } for(int i = 0; i <= iterator; i++) { totalInfected += roads[i].length; } return totalInfected; } int main() { std::ios_base::sync_with_stdio(false); int t; cin >> t; for(int i = 0; i < t; i++) { int n; string citiesState; cin >> n; cin >> citiesState; cout<<task(n, citiesState)<<endl; } return 0; } |