Aggressive cows POJ - 2456 题解

左手的ㄟ右手 2022-09-02 04:26 175阅读 0赞

# 题目链接 #

[点击这里][Link 1]

## 代码 ##

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int N, M;
    const int MAX_N = 100000;
    int X[MAX_N];
    
    bool try_place(int mid)
    {
        
    	int pre = 0;
    	int cnt = 1;
    	for (int i = 1; i < N; ++i)
    	{
        
    		if (X[i] - X[pre] >= mid)
    		{
        
    			pre = i;
    			++cnt;
    		}
    	}
    	return cnt >= M;
    }
    
    void solve()
    {
        
    	sort(X, X + N);
    	int min_length = 0;
    	int max_length = 1000000000;
    	while(max_length - min_length > 1)
    	{
        
    		int mid = (min_length + max_length) / 2;
    		// << mid << endl;
    		if (try_place(mid))
    		{
        
    			min_length = mid;
    		}
    		else
    		{
        
    			max_length = mid;
    		}
    	}
    	cout << min_length << endl;
    }
    
    int main()
    {
        
    	cin.sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	
    	cin >> N;
    	cin >> M;
    	for (int i = 0; i < N ; ++i)
    	{
        
    		cin >> X[i];
    	}
    	
    	solve();
    	return 0;
    }

## 总结 ##

这是一个简单的算法题，主要是基于二分法的思想，对两牛之间的最小距离最大化，对这个值进行二分。

每次二分的结果，都需要遍历一次数组来判断是否能够满足条件。

这里简述一下思想，就是现将牛进行排序，利用sort进行排序，复杂度(nlog(n))

之后，利用排序后的结果进行简单的判断，在第一个位置放第一头牛，在至少间隔你每个二分结果的距离上放第二头牛，看看能否放大于你要放的牛的数量，如果能放大于你要放的牛的数量，就减小上界，如果不能，就增大下届，知道找到一个最优的确定整数值，作为问题的结果输出即可。

### 随便写写的番外 ###

好久没写算法了，都显得生疏了，今天买了一个新的键盘，来试试手，竟然感觉这种简单的算法题都不是很流畅了，以后多练练，把状态找回来。

这里不得不推荐一下 ，两款必备的键盘，我都亲身体验过，一款是比较适合打游戏的，icbk的c87系列，青轴，真的好用。

另一款，就是我现在手里的这款键盘了——宁芝的静电容键盘，适合办公使用，35g最新的T系列，打字是真的不累，甚至是一种享受了，跟网上传闻的高级薄膜键盘真的不一样，至少也得说是顶级薄膜了吧，因为其他薄膜根本没有可比性，静电容绝对比其他的薄膜键盘好得多了。

对于办公来说，绝对是退烧级键盘了，拿来办公一整天手指都不会很累，以后我这两款键盘就满足了，成功退烧。

祝大家认真工作与学习，一起共同加油，共同进步。

[Link 1]: https://vjudge.net/problem/POJ-2456