杭电多校第十场 1011 Task Scheduler 题解

题目大意

有m个工人在线，k个工人不在线，有n个任务需要分配，每个任务需要$t_i$个工人，工人是随机选择的，选择到不在线的工人会重新选择，求最小分配期望的分配方案，且满足字典序最小。

解题思路

怎么总是出这种题啊。。

很烦，不怎么会写。

解题方法，如果k不等于0，则把1~n按照$t_i$大小，按照降序排列。

如果k为0，则直接输出1~n。

需要注意，需要用stable_sort，保证大小相同的值的相对位置不变，这样才能使字典序最小。

补充链接，排序并保留索引。

证明不会证了。。（丢人。

直接上大佬的博客。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 110;
int ans[N];
vector<int>  t;

int cmp(int a, int b) {
	return t[a] > t[b];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    //freopen("D:\\测试用\\in.txt", "r", stdin);
    //freopen("D:\\测试用\\out.txt", "w+", stdout);
	int T; cin >> T;
	while (T--) {
		int n, m, k; cin >> n >> m >> k;
		t.clear();
		for (int i = 0; i < n; i++) {
			int x; cin >> x; t.push_back(x); ans[i] = i;
		}
		if (k)	stable_sort(ans, ans + n, cmp);
		for (int i = 0; i < n - 1; i++) {
			cout << ans[i] + 1 << ' ';
		}
		cout << ans[n - 1] + 1 << endl;
	}
	return 0;
}