首页 > 其他分享 >poj 2010(优先队列)

poj 2010(优先队列)

时间:2023-05-29 19:35:42浏览次数:59  
标签:满足条件 题意 队列 调大 中位数 满足 poj 枚举 2010


题意: 奶牛大学:奶大招生,从C头奶牛中招收N头。它们分别得分score_i,需要资助学费aid_i。希望新生所需资助不超过F,同时得分中位数最高。求此中位数。


解题思路:这里要求最大中位数,中位数肯定是在这些人中间,故可以枚举中位数,可以先对分数进行排序,然后用二分去找最大中位数。

每次枚举的中位数应该要检验是否满足题意:

这里有一个check函数,它的返回值含义如下:



-1 直接输出,不可能满足条件了

0 这种方案是满足条件的,可以把中位数调大试试

1 这种方案是不满足的,但是把中位数调大就有可能满足了(否则不可能满足)

2 这种方案是不满足的,但是把中位数调小就有可能满足了(否则不可能满足)



标签:满足条件,题意,队列,调大,中位数,满足,poj,枚举,2010
From: https://blog.51cto.com/u_16143128/6373660

相关文章

  • poj 1948(搜索+剪枝)
    解题思路:这道题看到数据量,想到应该搜索+剪枝应该可以过。。可是别人的A了,我的却超时了。。。我用了一个mark[a][b],表示前两条边长度分别为a和b时,是否已经处理过,如果是的话就直接跳出。。。剩下的就是一个比较简单的搜索过程了,代码不难写,但是确实超时不可避免。。#include<iostream>......
  • poj 1604
    题意:计算n!最后一位不为0的数解题思路:1*2*3*......*n,每次乘完一个数后,把末尾0去掉,然后模上一个数,这样算出来的数肯定是最后一位不为0的数。。注意这里模的数不能太小,同时也不能太大,太小可能会影响乘积的效果,譬如可能出现0的情况被之前的模运算给抹掉了,太大就直接溢出了。。。参考了......
  • poj 2078(搜索+剪枝)
    解题思路:可以一行一行地递归求解,要是不符合条件就回溯,注意最后一行不能够移动它,因为可能会与之前重叠。。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintmaxn=8;intn,mat[maxn][maxn],ans;intget_max(intdep){ intm=......
  • poj 1324(BFS+状态压缩)
    解题思路:这道题一开始的想法就是状态压缩,即考虑如何判重,由于蛇并非是直线的,所以想到了以每一个点的上下左右共四个值来表示相对位置。最开始想如何用四进制来表示它,无语。。。。。还是题目做少了,直接用两位来表示一个点即可(两位的二进制数可以表示0-3)。剩下的关键就是判断蛇头会不......
  • poj 1195(二维树状数组)
    解题思路:这是一道很裸的二维树状数组AC:#include<stdio.h>#include<string.h>#defineN1100intc[N][N],n,arr[N][N];intlowbit(intx){returnx&(-x);}voidupdate(intx,inty,intnum){inti,j;for(i=x;i<=n;i+=lowbit(i))for(j=y;......
  • POJ 1505(二分+贪心)
    题意:给一些书,这些书有不同的页数,让把这些书分成k份,必须是连续的,问这些份中页数和的最大值最小是多少。解题思路:知道了页数和的范围,而且书都是连续的,要找到页数和最大值的最小值可以直接二分答案。。AC:#include<iostream>#include<cstdlib>#include<cstring>usingnamespacestd......
  • poj 3411(DFS多点访问)
    题意:有n座城市和m(1<=n,m<=10)条路。现在要从城市1到城市n。有些路是要收费的,从a城市到b城市,如果之前到过c城市,那么只要付P的钱,如果没有去过就付R的钱。求的是最少要花多少钱。解题思路:这道题的n与m都很小,dfs可以搞定,但这里与以往的搜索不同,以前dfs每个节点只能够访问一次,这里有多次访......
  • 数据结构之环形队列
    @TOC一.环形队列的定义及其特点循环队列是一种线性数据结构,其操作依然是先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。特点:对于一个普通队列来说,每出队一次,头指针就必须往后移一位,这样使用过的空间就无法再重复使用,(头指针无法回移),即使队列元素......
  • hdu 5102(队列+节点扩展)
    TheK-thDistanceTimeLimit:8000/4000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)ProblemDescriptionGivenatree,whichhasnnodeintotal.Definethedistancebetweentwonodeuandvisthenumberofedgeontheirunique......
  • 关于消息队列的一些思考
    日志与消费队列消息队列的应用价值数据集成于系统解耦异步处理与事件驱动流量削峰事务消息与分布式事务的最终一致从历史看消息队列的价值演化思考手上的工作,找到他的价值和定位,将价值最大化1.日志和消息队列推荐文章:TheLog:Whateverysoftwareengineershou......