CodeForces - 1007A Reorder the Array (改版田忌赛马) | 贪心算法+STL排序

题目:

Reorder the Array

 CodeForces - 1007A 

You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array [10,20,30,40][10,20,30,40], we can permute it so that it becomes [20,40,10,30][20,40,10,30]. Then on the first and the second positions the integers became larger (20>1020>10, 40>2040>20) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals 22. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.

Input

The first line contains a single integer nn (1≤n≤1051≤n≤105) — the length of the array.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the elements of the array.

Output

Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.

Examples

Input

7
10 1 1 1 5 5 3

Output

4

Input

5
1 1 1 1 1

Output

0

Note

In the first sample, one of the best permutations is [1,5,5,3,10,1,1][1,5,5,3,10,1,1]. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.


题意:

  给你一个序列,你可以生成这个序列的任意一个排列,对于某个排列,如果这个排列上某个位置的值大于原序列的值,那么就会产生1的贡献,问你最大能有多少贡献。新版田忌赛马!自己的马和自己的马比赛,最多赢几场。


思路:

  先进行排序,然数列呈从小到大分布,用 sort 。之后利用贪心思想,从大到小逐个判定。


题解:

#include <bits/stdc++.h> 
using namespace std;
int main() {
	int a; 
   scanf("%d",&a);
   int j=a-2,k=0;
   int b[a];
   int i=0; 
   for(;i<a;i++){
   scanf("%d",&b[i]);
   }
   sort(b,b+a);
   i--;
   for(;j>=0;){
   		if(b[i]>b[j]){
   			i--;j--;k++;
		   }else{
		   	j--;
		   }
   	
   }
   printf("%d\n",k);
    return 0;
}

 

全部评论

相关推荐

05-26 22:25
门头沟学院 Java
Java小肖:不会是想叫你过去把你打一顿吧,哈哈哈
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务