解法
roomSize = 3
leaders = {1, 4, 6, 10}
■所在不明者2, 3はどの部屋??
leaderが1の部屋に入っているだろう。
答え = 1
■所在不明者5はどの部屋??
leaderが1, 4のどれかの部屋に入っているだろう
しかし、leaderが1の部屋は2, 3が入っているだろうから人数パンパンである。
↓
leaderが4の部屋に入っているだろう
答え = 1
■所在不明者7, 8, 9はどの部屋??
leaderが1, 4, 6のどれかの部屋に入っているだろう
しかし、leaderが1の部屋は2, 3が入っているだろうから人数パンパンである。
↓
leaderが4, 6の部屋に入っているだろう
答え = 2
■所在不明者11, 12はどの部屋??
leaderが1, 4, 6, 10のどれかの部屋に入っているだろう
しかし、leaderが1, 4, 6の部屋は2, 3, 5, 7, 8, 9が入っているだろうから人数パンパンである。
↓
leaderが10の部屋に入っているだろう
答え = 1
class FindingFriend {
public:
int find(int roomSize, vector<int> leaders, int friendPlace) {
int roomCount = leaders.size();
for (int i = 0; i < roomCount; i++) {
if (leaders[i] == friendPlace) return 1;
}
sort(leaders.begin(), leaders.end());
int emptyCount = 0;
int rem = 0;
for (int i = 0; i < roomCount - 1; i++) {
emptyCount++;
rem += roomSize;
if (friendPlace < leaders[i + 1]) return emptyCount;
rem -= leaders[i + 1] - leaders[i];
if (rem == 0) emptyCount = 0;
}
return emptyCount + 1;
}
};