`
lilisalo
  • 浏览: 1131866 次
文章分类
社区版块
存档分类
最新评论

POJ 3258 二分算法

 
阅读更多

题目链接:http://poj.org/problem?id=3258

题意:有一条河流,上面原来有n个石头,FJ的cow可以从这些石头上跳过去,现在FJ想训练他的cow的跳跃能力,于是乎想移去其中的m个石头,而且他要求,去掉这m个石头后,石头与石头之间的最小值必须最大。

思路:二分答案,然后验证当前答案下最少需要移去的石头数量

my ugly code:

Source Code

Problem: 3258 User: bingshen
Memory: 324K Time: 172MS
Language: C++ Result: Accepted
  • Source Code
    #include<stdio.h>
    #include<algorithm>
    
    using namespace std;
    
    int dis[50005];
    int n,m;
    
    int slove(int mid)
    {
    	int res=0,temp=0,i,pre=0;
    	for(i=1;i<=n;i++)
    	{
    		if(dis[i]-dis[pre]<mid)
    			res++;
    		else
    			pre=i;
    	}
    	return res;
    }
    
    int max(int a,int b)
    {
    	if(a>b)
    		return a;
    	else
    		return b;
    }
    
    int main()
    {
    	int i,left=0,right=0,mid,l;
    	while(scanf("%d%d%d",&l,&n,&m)!=EOF)
    	{
    		left=99999999;
    		right=0;
    		for(i=1;i<=n;i++)
    			scanf("%d",&dis[i]);
    		dis[n+1]=l;
    		n++;
    		sort(dis+1,dis+n+1);
    		for(i=1;i<=n;i++)
    		{
    			if(dis[i]-dis[i-1]<left)
    				left=dis[i]-dis[i-1];
    		}
    		right=l;
    		while(left<=right)
    		{
    			mid=(left+right)>>1;
    			int temp=slove(mid);
    			if(temp>m)
    				right=mid-1;
    			else
    				left=mid+1;
    		}
    		printf("%d/n",right);
    	}
    	return 0;
    }
    
分享到:
评论

相关推荐

    POJ算法题目分类

    * 哈希表和二分查找等高效查找法:哈希表和二分查找等高效查找法是指解决问题的高效查找算法,如 poj3349、poj3274、POJ2151、poj1840、poj2002、poj2503。 * 哈夫曼树:哈夫曼树是指解决问题的哈夫曼树算法,如 poj...

    北大POJ初级-基本算法

    2. **查找算法**:线性查找、二分查找,以及哈希表的查找操作,这些都是在处理数据时常见的效率提升手段。 3. **递归与分治策略**:递归算法是解决复杂问题的有效方式,如斐波那契数列、汉诺塔问题等;分治策略常...

    poj题目分类

    * 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树:例如 poj3253。 * 堆:例如 poj2513。 * trie 树:例如 poj2513。 4. 简单搜索: * 深度优先搜索...

    poj 百练 题目分类

    在 POJ 百练 题目分类中,枚举类题目包括生理周期(2977)、称硬币(2692)、完美立方(2810)、熄灯问题(2811)、讨厌的青蛙(2812)、计算对数(2739)、数字方格(2747)、画家问题(2813)、拨钟问题(2814)、...

    算法分类以及POJ题目分类

    2. 1050 To the Max:求解最大值问题,可能需要构建一个二维数组来存储子问题的解。 3. 1125 Stockbroker Grapevine:涉及股票交易策略,需要考虑时间序列上的决策。 4. 1141 Brackets Sequence:与括号匹配相关,...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj3273, poj3258, poj1905, poj3122 - **解释**:概率统计问题通常涉及计算某个事件发生的概率。 ### 五、数值计算 #### 1. 数值分析 - **例题**:未列出具体题目 - **解释**:数值分析涉及数值计算...

    poj各种分类

    包括最长公共子序列、最优二分检索树等问题,关键在于状态转移方程的设计。 ### 六、数学 #### 组合数学 涵盖加法原理、乘法原理、排列组合等,用于解决计数问题,如poj3252。 #### 数论 涉及素数检测、整除性、...

    POJ各题算法分类和题目推荐 ACM必看

    POJ算法分类和题目推荐指南 本资源主要介绍了POJ(Online Judge)平台上各种算法分类和推荐题目,涵盖了动态规划、模拟、博弈等多种类型。以下是详细的知识点说明: 一、动态规划 动态规划是一种非常重要的算法...

    经典 的POJ 分类

    - POJ 3373、POJ 1691:二分查找技术的应用。 ### 动态规划 #### 二维动态规划 - **题目示例**: - POJ 1191、POJ 1054:基于矩阵的状态转移方程。 - POJ 3280、POJ 2029:多维状态空间的探索。 #### 递归动态...

    POJ练习题算法分类

    - **10.1-10.35** 包括了查找算法相关的题目,如第2678题可能是关于线性查找的问题,第2688题可能考察二分查找等。 #### 11. 时间复杂度 - **11.1-11.7** 关于时间复杂度的分析和计算,如第2712题可能涉及简单的...

    POJ题目简单分类(ACM)

    - **哈希表和二分查找**:提高查找效率,如poj3349,用于快速定位元素。 - **哈夫曼树**:压缩编码,如poj3253。 - **堆**:如优先队列,用于实现最大值或最小值的快速访问。 - **trie树**:用于高效字符串查询...

    强大的poj分类

    **简介**:基础算法是算法学习的基础,主要包括排序算法(如冒泡排序、选择排序、插入排序、归并排序、快速排序)、查找算法(如顺序查找、二分查找)、数学算法(如质数判断、最大公约数计算)等。 **重要性**:...

    强大的POJ分类——各类编程简单题及其算法分类

    4. **哈希表** 和 **二分查找**:提供高效查找能力,如POJ3349、3274、2151、1840、2002和2503。 5. **哈夫曼树**:用于压缩编码,如POJ3253。 6. **堆**:用于优先队列和部分排序问题。 7. **Trie树**:用于字符串...

    ACM常用算法及其相应的练习题.docx

    - poj3273, poj3258, poj1905, poj3122 七、计算几何学 * 几何公式 * 叉积和点积的运用:poj2031, poj1039 * 多边型的简单算法:poj1408, poj1584 * 凸包:poj2187, poj1113 中级部分: 一、基本算法 * C++的...

    poj训练计划.doc

    根据给定的文件信息,我们可以总结出一份详细的IT知识训练计划,主要针对编程竞赛和算法学习,特别是聚焦于POJ(Problem Online Judge)平台上的题目训练。这份计划分为两个阶段,初级阶段和中级阶段,共计涉及了165...

    acm训练计划(poj的题)

    - 提供对排序和查找算法的理解与应用指导,包括快速排序、归并排序、二分查找等经典算法。 4. **贪心算法**: - (poj3295):讲解如何利用贪心策略来解决问题,强调每一步选择都是局部最优解。 5. **动态规划**:...

    POJ1837-Balance

    解题的关键在于理解和应用适合的算法,比如动态规划、二分查找、平衡树操作等。在分析解题报告时,我们可以学习到如何分析问题、选择合适的算法,并在实际编程中实现这些思想。而AC代码则提供了具体的实现参考,展示...

    史上最全poj题目分类(159页).pdf

    通过以上分析,我们可以看到文档中提及的【史上最全poj题目分类(159页)】包含了丰富的编程题目资源,涉及算法竞赛和编程技能训练的多个方面。通过动态规划和参与各类算法竞赛的训练,可以有效提升解决实际问题的能力...

    poj图论题目汇总

    - **知识点**:二分匹配是解决一类特定问题的有效算法,特别是当问题可以被建模为一个二分图时尤为有效。 - **二分图**:一种特殊的图,其中顶点可以被分为两个不相交的集合,每条边都连接两个不同集合中的顶点。 ...

    ACMer需要掌握的算法讲解 (2).docx

    * 哈希表和二分查找等高效查找法:POJ3349、POJ3274、POJ2151、POJ1840、POJ2002、POJ2503 * 哈夫曼树:POJ3253 * 背包问题:POJ1837、POJ1276 * DP算法:POJ3267、POJ1836、POJ1260、POJ2533 二、图算法 * 度限制...

Global site tag (gtag.js) - Google Analytics