贪心

课程讲义链接： http://oj.mqcoj.cn:5000/paste/show/VzZXbx10fZdsPv8a

/*
  对于每一个要插入的数字
  0. 先从小到大排序
  1.先找现有的分组中，有没有这个数可以插入的地方
  2. 如果有多个可插入的为止，选择长度最小的一个组
  3. 如果没有，新建立一个组别
 */

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a[N];
struct node {
	// num 记录这个组别的数字的数量
	// sl 队列的最后一个数字
	int num, sl;
};
node team[N];   // 用来记录组别的信息
int mark; // 记录组别的数量
// map[a[i]]  以  a[i] 结尾的组别在优先队列中的编号为 map[a[i]]
map<int, int> mp;
// q[i] 以  i 结尾的
// 优先队列记录 <队员数量，组别编号>
priority_queue<pair<int, int> > q[N];  // 优先出队员数量最少的，前面加负号
int tot; // 记录优先队列的组别
void insert(int k) {
	// 现在要插入 k
	if (mp[k - 1] == 0) { // 当前没有以 k-1 结尾的
		++mark; // 新增一个组别，记录
		team[mark].num = 1;
		team[mark].sl = k; // 当前数字以 k  结尾
		// 先去判断有没有以 k 结尾的
		if (mp[k] == 0) {
			tot++;
			mp[k] = tot;
			q[tot].push({-1, mark});   // 记录他的值和他的组别
		} else {
			q[mp[k]].push({-1, mark}); // 放在之前的优先队列中
		}
	} else { // 有以 k -1 结尾的队列
		int t = mp[k - 1];
		int top = q[t].top().second; // 获取到以 k-1 结尾的队列中数量最小的的在 team 数组中的编号
		q[t].pop();
		if (q[t].size() == 0) mp[k - 1] = 0; // 当前 k-1 只有一个，出完了，归0
		// 现在变成以 k 结尾
		team[top].num++;
		team[top].sl = k;
		// 放置到 以 k 结尾的队列中
		// 先去判断有没有以 k 结尾的
		if (mp[k] == 0) {
			tot++;
			mp[k] = tot;
			q[tot].push({-team[top].num, top});   // 记录他的值和他的组别
		} else {
			q[mp[k]].push({-team[top].num, top}); // 放在之前的优先队列中
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	for (int i = 0; i < n; i++)
		insert(a[i]);
	// 组别编号是从 0 开始的
	int ans = team[1].num;
	for (int i = 1; i <= mark; i++)
		ans = min(ans, team[i].num);
	cout << ans;
	return 0;
}

加工生产调度

//// 时间：产品a 机器，b 机器
//产品1  a1 10 , b1  21
//产品2  a2  5,  b2  3
//
//a1 + b1 大的在前面 ， 作为一个贪心策略
//1 - 2:  10 + 21 + 3 = 34    正解
//2 - 1:  5 + 10 + 21 = 36
//
//反例？？？ ， 找到一个策略，去找反例，看能不能推翻
//能推翻，策略肯定是错的，不能推翻，不一定是对的？
//产品1  a1  10 , b1  4
//产品2  a2  5,  b2  6
//1 -2 :10 + 5 + 6  = 21
//2 -1 :5 + 10 + 4 = 19    正解
//
//加工产品，先在A 上面，再在B 上面
//尽快从 A 走到B，能更快完成，
//
//N1 表示  a<b 的任务列表　
//  大家都是  a<b  ,先完成谁？？？？？？　优先完成　ａ　小的
//a1 5  b1 8
//a2 4  b2 8
//1+2 : 5+8+8
//2+1 : 4+8+8


//N2 表示 a>b 的任务列表, 优先完成 b 大的
// a1 10  b1 8
//// a2 10  b2 9
//1+2: 10 + 10 + 9
//2 + 1 : 10 + 10 + 8


//最优的策略是  N1 + N2

//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

struct node {
	int a, b;
	int id;
};

bool cmp1(node a, node b) {
	return a.a < b.a;
}

bool cmp2(node a, node b) {
	return a.b > b.b;
}

node a[N], b[N];
int la, lb;
int n, t[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i];
	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		if (tmp <= t[i]) {
			b[++lb].a = t[i];
			b[lb].b = tmp;
			b[lb].id = i;
		} else {
			a[++la].a = t[i];
			a[la].b = tmp;
			a[la].id = i;
		}
	}
	sort(a + 1, a + 1 + la, cmp1);
	sort(b + 1, b + 1 + lb, cmp2);
	// 计算时间
	// 一个任务是有 a 的时间和 b 的时间
	int cnt = 0;
	int ta = 0, tb = 0; // 记录上一个任务的完成时间
	for (int i = 1; i <= la; i++) {
		t[++cnt] = a[i].id;  // 完成顺序
		ta += a[i].a;
		// 1.
		// tb = 10 , 上一个任务在 b 机器上的完成时间
		// ta = 9 ,  当前任务在 a 机器上的完成时间，
		// 任务准备好了，机器没有准备好
		// 当前任务在 b 机器上的开始时间，  10

		// tb = 10 , 上一个任务在 b 机器上的完成时间
		// ta = 15 ,  当前任务在 a 机器上的完成时间，
		// 机器准备好了，但是任务没有准备好
		// 当前任务在 b 机器上的开始时间， 15

		tb = max(ta, tb) + a[i].b;
	}

	for (int i = 1; i <= lb; i++) {
		ta += b[i].a;
		tb = max(ta, tb) + b[i].b;
		t[++cnt] = b[i].id;  // 完成顺序
	}

	cout << tb << endl;
	for (int i = 1; i <= n; i++)
		cout << t[i] << " ";

	return 0;
}

序列排序

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define int long long
int n, a[N], c[N], tmp[N];
bool vis[N];
int k = 1e9;// 全局最小值
int sum, cnt, minn, ans; // 环内的和，个数，最小值

void dfs(int i) {
	sum += a[i];
	minn = min(minn, a[i]);
	cnt++;
	vis[i] = 1;
	if (vis[c[i]])
		return ;
	dfs(c[i]);
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		tmp[i] = a[i];
		k = min(k, a[i]);
	}
	sort(tmp + 1, tmp + 1 + n);

	for (int i = 1; i <= n; i++)
		c[i] = lower_bound(tmp + 1, tmp + 1 + n, a[i]) - tmp;

	for (int i = 1; i <= n; i++) {
		if (vis[i])
			continue;
		sum = 0, cnt = 0, minn = 1e9;
		dfs(i);
		int t1 = sum + minn * (cnt - 2);
		int t2 = sum + k * (cnt + 1) + minn;
		ans += min(t1, t2);
	}
	cout << ans;
	return 0;
}