Mad cow

The time limit :1000 ms  |  Memory limit :65535 KB
difficulty :4
 
describe
Farmer John Built a long corral , It includes N (2 <= N <= 100,000) Compartments , The compartments are numbered in turn x1,...,xN (0 <= xi <= 1,000,000,000).
however ,John Of C (2 <= C <= N) The cows don't like this layout , And a few cows in a cubicle , They're going to fight . In order not to let cattle hurt each other .John Decide to allocate compartments to the cattle , Make the minimum distance between any two cows as large as possible , that , What is the maximum and minimum distance ?
 
Input
Multiple sets of test data , With EOF end .
first line : Two integers separated by spaces N and C
The second line —— The first N+1 That's ok : It is pointed out that xi The location of
Output
Each group of integers outputs one test data , Satisfy the maximum and minimum of the meaning of the problem , Pay attention to the new line .
The sample input
5 3
1
2
8
4
9
Sample output
3

#include <iostream>
#include <algorithm>
using namespace std;

long long a[1000000];
int n,c;

bool Judge(int mid)
{
int i,sum=1,temp=a[0];// At least one cow
for(int i=1;i<n;i++)
{
if(a[i]-temp>=mid)// The distance from the first room number is once
{
sum++;
temp=a[i];// to update temp Value ,temp To a[i] You can put down a cow in between . temp=a[i], Ask for the next a[i] To temp No, you can put down a cow
if(sum>=c)// If the total sum>c, You can put it down c Head ox
return true;
}
}
return false;
}

int Binary_search()// The maximum of the minimum distance of binary search
{
int min=0,max=a[n-1]-a[0],mid=0;
while(min<=max)
{
mid=(max+min)/2;// Take the value between the minimum distance and the maximum distance first
if(Judge(mid))// If the current distance can be lowered c Head ox
min=mid+1;// Try to increase the minimum distance @
else
max=mid-1;// can't let go , It has to be reduced mid Value
}
return min-1;// because @ It's about min+1, So here minus one
}

int main()
{
while(cin>>n>>c)
{
for(int i=0;i<n;i++)
cin>>a[i];// The position of the smallest number
sort(a,a+n);// Sort these minimum numbers in ascending order
cout<<Binary_search()<<endl;
}
return 0;
}

nyoj More about mad cow

  1. poj 2456 Aggressive cows &amp;&amp; nyoj Mad cow Maximize the minimum Two points

    poj 2456 Aggressive cows && nyoj Mad cow Maximize the minimum Two points Topic link : nyoj : http://acm.nyist.net/JudgeOnline/ ...

  2. NYOJ 1007

    In blogs NYOJ 998 Three ways to compute Euler functions have been written in , No more details here . This problem is also an examination of the application of Euler function , However, another fundamental theorem of number theory is examined : How to use Euler function to find less than n And with the n The sum of all positive integers of Coprime . remember eule ...

  3. NYOJ 998

    This problem is the use of Euler function , Here's a brief introduction to Euler functions . Euler function is defined as : For positive integers n, Euler function means no more than n And with the n The number of Coprime positive integers . Properties of Euler functions :1. set up n = p1a1p2a2p3a3p4a4...pk ...

  4. NYOJ 333

    http://www.cppblog.com/RyanWang/archive/2009/07/19/90512.aspx?opt=admin Euler function E(x) Representation ratio x Small and related to x The number of Coprime positive integers . ...

  5. NYOJ 99 Word splicing ( Euler of a digraph ( return ) road )

    /* NYOJ 99 Word splicing : Ideas : Search for Euler circuits or Euler paths ! Be careful : It's digraph ! Don't think of it as an undirected graph , Otherwise, in the judgment before the search, it will lead to unnecessary search , So that TLE! Euler paths of digraphs :abs(In[i ...

  6. nyoj 10 skiing Search for + Kinesiology

    It's been two days , Can't open a web page , I submitted too many times ? nyoj 10: #include<stdio.h> #include<string.h> ][],b[][]; int ...

  7. ACM Mad cow

    Mad cow The time limit :1000 ms  |  Memory limit :65535 KB difficulty :4   describe Farmer John Built a long corral , It includes N (2 <= N <= 100,000) Compartments , These are small ...

  8. Short answer: hash implementation (nyoj 138 Look for the ball number 2)

    Example Links :http://acm.nyist.net/JudgeOnline/problem.php?pid=138 Code purpose : Review hash with Code implementation : #include "stdio.h&qu ...

  9. nyoj 284 Tanks war Simple search

    Topic link :http://acm.nyist.net/JudgeOnline/problem.php?pid=284 The question : In a given graph , Iron wall , The river cannot go , If the brick wall goes away , Spend more time 1, Ask from the beginning to the end at least ...

Random recommendation

  1. java Save the file locally

    private void savePic(InputStream inputStream, String fileName) { OutputStream os = null; try { Strin ...

  2. Java in String,StringBuffer And StringBuilder The difference between

    String String constant : StringBuffer String variable 〈 buffer 〉( Thread safety ): StringBuilder String variable 〈 buffer 〉( Non-thread safety ): In a nutshell , String The type and Strin ...

  3. jQuery Overall framework

    Chapter one    Overall framework 1. Design concept jQuery The idea is “ Write less code , Do more ”, And make the code highly compatible . 2. Overall framework It can be roughly divided into three parts : Building blocks , The underlying support module and function module . 3. Use self invocation ...

  4. hdu 4739 2013 Hangzhou district network competition Looking for parallelogram **

    It's parallel to the axis , Just sort it out , Oh my god , Water is not good If it's not parallel , You need to judge by the length of the side

  5. Oracle Stream replication practice notes

    Recently, because of business needs , Need to do two-way real-time synchronization between the two databases , So I put it into practice Oracle Stream replication of , Encountered a lot of difficult problems , In the end, it looks like success , It is recorded as follows . I use it. OEM To achieve stream replication . 10. Two databases for stream replication ...

  6. Compressed sensing ( twenty-five ): Piecewise orthogonal matching pursuit of compressed sensing reconstruction algorithm (StOMP)

    primary coverage : StOMP Algorithm flow of StOMP Of MATLAB Realization Experiments and results of one-dimensional signals Threshold parameters Ts. Measurements M Experiments and results on the relationship between reconstruction success probability and reconstruction success probability One .StOMP Algorithm flow of Piecewise orthogonal matching pursuit (Stagewis ...

  7. Picture view h5

    @{ Layout = null; } <html> <head> <script type="text/javascript" src=" ...

  8. [one day one question] Vue Array changes cannot trigger refresh

    Problem description :Vue Array changes cannot trigger refresh , Especially when every element of an array is an object , The value of an attribute in an object changes , There's no way to trigger Vue Of dom Refresh , How can this be broken ? Solution :this.$set(array, index ...

  9. Sybase Database implementation is equivalent to mysql in group_concat function

    stay MySQL in , If you want to merge the grouped data into one column , have access to group_concat function , As shown in the figure below : however , stay Sybase There is no such function in ( Don't ask me why I use Sybase, Because the company uses Sybas ...

  10. Android Four common layouts ( Or five )

    One .FrameLayout( Frame layout ): Display features : All child controls are displayed by default in FrameLayout Top left corner of , It's going to overlap . Common properties : layout_gravity( Set to child controls , Adjust the weight of the control in the container ...