CFCF2176A.Operations with Inversions
普及-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定一个数组 a1,a2,…,an。每次操作,你可以选择一对下标 i,j,满足 1≤i<j≤n,ai>aj,并且从数组中删除下标为 j 的元素。操作后,数组的大小减少 1,元素的相对顺序不变。
请你判断,在最优策略下,最多可以进行多少次这样的操作。
输入格式
每个测试包含多个测试用例。第一行为测试用例的数目 t(1≤t≤50)。接下来是测试用例的描述。
每个测试用例的第一行为一个整数 n(1≤n≤100)——数组的初始长度。
每个测试用例的第二行为 n 个自然数 a1,a2,…,an(1≤ai≤n)。
输出格式
对于每个测试用例,输出在给定数组上最多能够进行的操作次数。
输入输出样例
输入#1
5 3 3 2 1 3 1 2 3 3 3 3 3 5 3 1 4 5 2 1 1
输出#1
2 0 0 2 0
说明/提示
在第一个样例中,可以首先选择下标为 i=2,j=3 的一对,值分别为 a2=2,a3=1,并删除 a3。此时数组变为 a=[3,2]。之后可以通过选择 i=1,j=2 再次删除第二个元素。操作总次数为 2。
在第二、第三和第五个样例中,无法进行任何操作,因为没有符合条件的下标对。
在第四个样例中,可以删除第二个和第五个元素。可以证明,这就是最优答案,不存在能够删除更多元素的方案。