洛谷P10387 [蓝桥杯 2024 省 A] 训练士兵

佚名 / 2024-10-11 / 原文

洛谷P10387 [蓝桥杯 2024 省 A] 训练士兵

1.My solution

#include <stdio.h>

#include <algorithm>
#include <cmath>
#include <iostream>
#include <set>
#include <string>
#define For(i, j, n) for (int i = j; i <= n; ++i)

template <typename T>
inline T read() {
    T x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

typedef long long LL;

constexpr int N = 1e5 + 5;

struct Soldier {
    int p, c;
    Soldier(int p, int c) : p(p), c(c) {}
	Soldier() : p(0), c(0) {}
    bool operator<(const Soldier& other) const { return c < other.c; }
} soldiers[N];

int n;
LL S, sumofP[N], sumofPC[N];

std::set<int> setofC;

int find(int x) {
	int l = 1, r = n;
	while(l < r) {
		int mid = l + r >> 1;
		if(soldiers[mid].c < x)
			l = mid + 1;
		else 
			r = mid;
	}
	return l;
} // 第一个大于等于x的值的位置

LL sumFromVal(int val) {
	int pos = find(val);
	return (sumofPC[n] - sumofPC[pos - 1]) - (LL)val * (sumofP[n] - sumofP[pos - 1]);
}

int main() {
    n = read<int>();
    S = read<LL>();
    for (register int i = 1; i <= n; i++) {
        int p = read<int>(), c = read<int>();
        soldiers[i] = Soldier(p, c);
        setofC.insert(c);
    }
    std::sort(soldiers + 1, soldiers + n + 1);
    for (int i = 1; i <= n; i++) {
        sumofP[i] = sumofP[i - 1] + (LL)soldiers[i].p;
		sumofPC[i] = sumofPC[i - 1] + (LL)soldiers[i].c * (LL)soldiers[i].p;
    }
    LL ans = 1000000000000000000LL;
    for (auto val : setofC) {
		LL tmpAns = S * val + sumFromVal(val);
		ans = std::min(ans, tmpAns);
    }
	printf("%lld\n", ans);
    return 0;
}

因为集体训练和单独训练的转折点肯定是某一批士兵训练完了之后，所以可以用set把c存起来，然后遍历一遍

2. Best solution

注意到c的取值范围比较小，故可以直接用一个桶存起来，这样更快

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL n, s, p[N], c[N], cnt[N], Sum, now, ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> s;
	for (int i = 1; i <= n; i++)
		cin >> p[i] >> c[i], cnt[c[i]] += p[i], now += p[i], Sum += p[i] * c[i];
	for (int i = 1; i <= 1e6; i++) {
		if (now < s)  break;
		ans += s;
		Sum -= now;
		now -= cnt[i];
	}
	cout << ans + Sum;
	return 0;
}