CF1008C Reorder the Array

    • 50通过
    • 69提交
  • 题目来源 CodeForces 1008C
  • 评测方式 RemoteJudge
  • 标签 排序
  • 难度 普及/提高-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目大意:

    给定一个序列,序列里的元素可以以任意顺序重新排好

    序列里某位置排序后的数可能会大于原数,问这样的位置最多能有多少个

    输入格式:

    第一行一个整数$n$,表示序列长度

    第二行$n$个整数,表示初始序列

    输出格式:

    一个整数,表示满足条件的位置最多能有多少个

    题目描述

    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] $ , we can permute it so that it becomes $ [20, 40, 10, 30] $ . Then on the first and the second positions the integers became larger ( $ 20>10 $ , $ 40>20 $ ) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals $ 2 $ . 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.

    输入输出格式

    输入格式:

    The first line contains a single integer $ n $ ( $ 1 \leq n \leq 10^5 $ ) — the length of the array.

    The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the elements of the array.

    输出格式:

    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.

    输入输出样例

    输入样例#1: 复制
    7
    10 1 1 1 5 5 3
    
    输出样例#1: 复制
    4
    
    输入样例#2: 复制
    5
    1 1 1 1 1
    
    输出样例#2: 复制
    0
    

    说明

    In the first sample, one of the best permutations is $ [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.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。