Description

给定一个长度为n的数组a，提供一种操作：

  • 每次操作从a选择任意长的子序列。
  • 设其子序列的平均数为AVG。
  • 然后删去子序列中大于AVG的值。

操作次数不限，求最多可删除的元素个数。

Constraints

  • 1≤n≤100
  • 1≤ai≤100

Solution

构造极端的做法。每次挑选全局最小的值和当前最大的值，显然当前最大的值要被删除。

最后只剩下全局最小的值，因此答案就是n−min_count。

Code

#include <bits/stdc++.h>
using namespace std;
namespace vs = views;

int main() {
    int T; cin >> T;
    for(auto _ : vs::iota(0, T)) {
        int min_value = 111;
        int min_count = 0;
        int n, temp;
        cin >> n;
        for(auto _ : vs::iota(0, n)) {
            cin >> temp;
            temp -= min_value;
            if(temp < 0) min_value += temp, min_count = 1;
            else if(temp == 0) min_count++;
        }
        cout << n - min_count << endl;
    }
}

Codeforces-1529A Eshag Loves Big Arrays