牛客月赛115 C题-命运之弹 题解

原题链接

https://ac.nowcoder.com/acm/contest/107879/C

题目描述

解题思路

记录每个数字出现的次数。枚举使用「转瞬即逝」的位置，统计后边比当前数字更大的数的数量，进而统计、更新答案。
详细细节见代码，代码里有详细的注释解释。

代码（CPP）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl "\n"
const int maxn = 2e5 + 10;
const int INF = 1e9;
int a[maxn], num[maxn], n;void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}int q;cin >> q;int v;      // 初始幸运值cin >> v;// 计数for (int i = 1; i <= n; i++) {num[a[i]]++;}// 枚举使用「转瞬即逝」的位置，统计后边比当前数字更大的数的数量即可int ans = INF;int cnt = 0;    // 统计前面大于v的数的个数for (int i = 1; i <= n; i++) {num[a[i]]--;// 统计后边比当前数字a[i]更大的数的数量即可int sum = 0;for (int j = a[i] + 1; j <= 100; j++) {sum += num[j];}// 统计答案，如果将当前数使用转瞬即逝，则本次代价为前面大于v的数的个数加上后边大于a[i]的数的数量ans = min(ans, sum + cnt);// 统计前面大于v的数的个数if (a[i] > v) cnt++;}cout << ans << endl;
}int main() {
//     freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}