Namely, it is possible that every slice is wanted by many people.
We can use the marriage theorem to fix this. If for any m slices, there are no less than m people such that each of them like at least one of these m slices, then the marriage condition is satisfied, and there is a perfect matching: everyone can get one slice he likes.
Otherwise, let m be the smallest number such that there are m slices and less than m people like at least one of them. Now we can do a match and let each of these people get one slice and go: others won't complain since they do not like any of these m slices, which means for them, each of these m pieces is less than 1/N and they think they are left enough.
Then this procedure continues until everyone is happy.
Great! There might be a problem, but can be fixed.
本帖于 2007-09-25 09:39:38 时间, 由普通用户 康MM 编辑