### talisman's blog

By talisman, history, 7 weeks ago,

I've come across this problem, I know that I'm going to binary search the answer (Given the fact that if x(time) is good, x + 1 is also good), but I am very stuck at how to determine if that time is good or not in the first place. Any help would be much appreciated. Thanks in advance,

• -1

 » 7 weeks ago, # |   0 Note that binary search allows you to change the varying factor. The original problem requires you to find the minimal T given a fixed m,which is difficult as you don't know how many balloons to assign for each assistant. Binary search is essentially choosing a fixed T and finding the maximal m every time,which is much simpler since the amount of balloons every assistant can inflate in a given time is easy to find. The way it works is just like what you have mentioned: if they can make m balloons in T minutes, then they must be able to do it in T+1 minutes.So keep in mind that binary search is transforming one hard problem into log(n) simple problems. My submission goes here, you are encouraged to write your own solution tho#include using namespace std; using ll = long long; int main() { ll reqBallonCnt, assistantCnt; cin >> reqBallonCnt >> assistantCnt; vector> assistants(assistantCnt); for (auto& [inflateTm, ballonCnt, restTm, tmPerRound] : assistants) { cin >> inflateTm >> ballonCnt >> restTm; tmPerRound = inflateTm * ballonCnt + restTm; } ll minTm = 0, maxTm = reqBallonCnt * 200; while (minTm < maxTm) { ll currTm = (minTm + maxTm) >> 1; ll maxBallonCnt = 0; for (ll i = 0; i < assistantCnt; i++) { auto [inflateTm, ballonCnt, restTm, tmPerRound] = assistants[i]; ll roundCnt = currTm / tmPerRound; ll remain = min(ballonCnt, (currTm - tmPerRound * roundCnt) / inflateTm); maxBallonCnt += ballonCnt * roundCnt + remain; } if (maxBallonCnt < reqBallonCnt) minTm = currTm+1; else maxTm = currTm; } vector maxInflatedCnts(assistantCnt); for (ll i = 0; i < assistantCnt; i++) { auto [inflateTm, ballonCnt, restTm, tmPerRound] = assistants[i]; ll roundCnt = minTm / tmPerRound; ll remain = min(ballonCnt, (minTm - tmPerRound * roundCnt) / inflateTm); maxInflatedCnts[i] = ballonCnt * roundCnt + remain; } cout << minTm << endl; for (ll i = 0; i < assistantCnt; i++) { ll realInflatedCnt = min(reqBallonCnt, maxInflatedCnts[i]); cout << realInflatedCnt << ' '; reqBallonCnt -= realInflatedCnt; } cout << endl; return 0; }