Skip to content

Instantly share code, notes, and snippets.

@alivesay
Created May 20, 2021 15:44
Show Gist options
  • Save alivesay/1030c0440b0fb8ea600ac3c19e7a8b94 to your computer and use it in GitHub Desktop.
Save alivesay/1030c0440b0fb8ea600ac3c19e7a8b94 to your computer and use it in GitHub Desktop.
int timeToCrossBridge(int* party, int partySize) {
if (partySize == 1) return party[0]; // 1 torch, 1 guy, no problem
if (partySize == 2) return party[1]; // easy
if (partySize < 1) return -1; // no party :(
int *p = &party[partySize - 1]; // p moves backwards from slowest
int *fastest = &party[0];
int *nextFastest = &party[1];
int time = 0;
int slowest = 0;
int mid = (partySize >> 1) - 1;
if (party[mid] << 1 > party[mid-1] + party[mid+1])
time += *(p--);
else
time += *nextFastest;
while (p != party) {
time += *fastest;
fastest = nextFastest;
time += *p;
nextFastest = p--;
if ((*p << 1) > *(p-1) + *(p+1))
fastest = &party[0];
else
if (p-- == party) break;
}
return time;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment