题目大意是在一个布满坑的地图上灌水，求最大储水量。
显然边界的坑是无法储水的，因此可以将边界的坑都加入一个保证坑的高度最小的优先队列（用二叉堆实现）。然后每次取出队列顶端的节点进行四个方向的灌水（如果高度比当前水位高度低则可增加储水量），将未曾加入队列的节点加入队列中继续这个过程直到队列为空即可。因为是从边界开始灌水，可以保证结果的正确性，同时显然可以确定每个坑只进出队列一次。故时间复杂度为O(nmlog(nm))。
7891534 IwfWcf 2227 Accepted 1288K 1719MS G++ 1631B 2010-11-18 18:22:05
题目大意是有n个人参加舞会，第i个人希望认识a[i]个朋友，初始每个人都没有朋友，问能否满足所有人的交友要求。
显然a[i]>=n，a[i]>=total(大于0的a[i]总数）以及∑a[i] mod 2<>0的可直接判无解。然后每次都按照交友量需求进行排序，从大到小分配，如果遇到无法分配的则可判无解。注意一定要保证每次分配的顺序都是从大到小，否则会WA。维护队列的有序性可以用Qsort也可以用堆，虽然建堆是线性的，但维护队列过程中的插入和删除操作使总的复杂度还是达到了O(nlogn)，所以用Qsort和用堆来维护队列的时间复杂度是相同的，编程复杂度Qsort更加简单。
3016349 2008-08-01 11:55:49 Accepted 2140 FPC 00:00.13 424K IwfWcf@LZOI
博文
所有评论
