上海计算机学会 2023年10月月赛 丙组T4 定价（贪心、排序）

第四题：T4定价

标签：贪心、排序
题意：有$n$个人来买一款商品，每个人都有对这个商品的最高预算$a_i$，商品价格超过预算就不买，反之就买。现要求定一个最优价格，使之总收入最大。
题解：很经典的一个贪心，先排序，排序完对每个预算进行枚举（作为当前的定价），因为排序，在第$i$个预算之后（包括第$i$个）的预算都是会买的，所以当前收入为$(n-i+1)\ast a_i$，维护一个最大值。
代码：

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

typedef long long ll;
ll a[200005];

int main() {
    ll n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, (n - i + 1) * a[i]);
    }
    cout << ans << endl;
    return 0;
}

第五题：T5先修课程

标签：拓扑排序
题意：教务处针对$n$门课程设置了$m$条约束条件，其中的第$i$条约束要求在学习第$y_i$门课程之前，必须先修完第$x_i$门课程。
请判断这些约束条件是否存在矛盾。如果没有矛盾输出$Valid$，否则输出$Invalid$。
题解：拓扑排序判环裸题，如果拓扑排序能够输出所有顶点，即无环，反之有环。（即判最终出来的顶点数是否为$n$个）
代码：

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

int n, m, u, v, in[200005];
vector<int> e[200005];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        in[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) q.push(i);
    }

    int cnt = 0;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < e[u].size(); i++) {
            v = e[u][i];
            in[v]--;
            if (in[v] == 0) q.push(v);
        }
    }
    if (cnt < n) cout << "Invalid";
    else cout << "Valid";
    return 0;
}