深信服230906

1. bfs
2. dp
3. 0, 没看懂题目, 没看懂样例是怎么计算好友的好感度, 后面蹲一下大佬的讲解
4. top k, 40, 今晚的教训是凡是top k都应该首先想到堆排

复盘第四题, 不知道能不能过, 在此留档

class Solution_230906_shenxinfu_4 {
// 给定若干个样例
// 每个样例中有若干个任务的耗时, 并指定需要做其中k个任务
// 需要对该样例的所有任务筛选, 选出最小耗时的k个任务, 同时保持相对顺序
// 对后面选出的k个任务进行切分, 分成左右两部分, 交给两个人做, 两个人同时开始做, 求总耗时最小是多少

// 230909
// pair的类型不能用pair<const int, int>
public:
	struct my_compare {
		bool operator()(const pair<int, int>& left, const pair<int, int>& right){
			if (left.first == right.first) {
				return left.second > right.second;
			}
			else {
				return left.first > right.first;
			}
		}
	};
	int func(vector<int>& times, int k) {
		// 1 寻找所有任务耗时中消耗最小的k个值
		// 2 前缀树切分

		// (num, index), 大顶堆
		priority_queue<pair<int, int>, vector<pair<int, int>>, my_compare> q;
		for (int index = 0; index < times.size(); ++index) {
			pair<int, int> temp = (times[index], index);
			q.emplace(temp);
			if (q.size() > k) {
				q.pop();
			}
		}

		// 回填k个值
		vector<int> retain(times.size(), 0);
		for (; !q.empty(); ) {
			pair<const int, int> temp = q.top();
			q.pop();
			retain[temp.second] = temp.first;
		}

		// 制作前缀表
		vector<int> prefix(times.size(), 0);
		prefix[0] = retain[0];
		for (int index = 1; index < prefix.size(); ++index) {
			prefix[index] = prefix[index - 1] + retain[index];
		}

		int result = INT_MAX;
		for (int index = 0; index < prefix.size(); ++index) {
			result = min(result, max(prefix[index], prefix.back() - prefix[index]));
		}
		return result;
	}
	// 入口摆在这里了
	void test() {
		int T;
		cin >> T;
		for (; T; --T) {
			int n, k;
			cin >> n >> k;
			vector<int> times;
			for (; n; --n) {
				int t;
				cin >> t;
				times.emplace_back(t);
			}
			cout << func(times, k) << endl;
		}
	}
};