IwfWcf's OI Log: ZJU/ZOJ 2140 Ball 解题报告

2008年8月1日星期五

题目大意是有n个人参加舞会，第i个人希望认识a[i]个朋友，初始每个人都没有朋友，问能否满足所有人的交友要求。

显然a[i]>=n，a[i]>=total(大于0的a[i]总数）以及∑a[i] mod 2<>0的可直接判无解。然后每次都按照交友量需求进行排序，从大到小分配，如果遇到无法分配的则可判无解。注意一定要保证每次分配的顺序都是从大到小，否则会WA。维护队列的有序性可以用Qsort也可以用堆，虽然建堆是线性的，但维护队列过程中的插入和删除操作使总的复杂度还是达到了O(nlogn)，所以用Qsort和用堆来维护队列的时间复杂度是相同的，编程复杂度Qsort更加简单。