Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

tdkhoa2018's blog

By tdkhoa2018, 3 months ago, In English,

Consider the following problem: for an array a no reduction of n elements, and an integer b is chosen arbitrarily, find the minimum value of

Solution:

Step1: Prove that b we need to find is equal to the value of a certain element in array a.

Step 2: Prove

Detail:

Step 1:

  • With then

  • With then

  • With then

Easy to see:

  • if then

  • if then

So we have proved that b is a certain element in array a.

Step 2:

Now that we know b is an element in array a, we temporarily set that element to .

Let smallest when smallest.

  • With then smallest when smallest.

  • With then smallest when biggest.

So we have found b satisfying and proved successful.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it