贪心

#include <bits/stdc++.h>
using namespace std;
const int N = 150;
int n;
int a[N][N], s[N][N];
int res = -2147483648;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			// 求每一列的前缀和
			s[i][j] = s[i - 1][j] + a[i][j];
			//cout << s[i][j] << endl;
		}
		//cout << endl;
	}

	// 枚举上下界
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			int maxx = s[j][1] - s[i - 1][1];  // 存储的是最大子段和
			for (int k = 2 ; k <= n; k++) {
				// 上界 是 i ,下界是 j , 是 第 k 列
				int tmp = s[j][k] - s[i - 1][k];
				//cout << maxx << " " << tmp << endl;
				maxx = max(maxx + tmp, tmp);
				res = max(res, maxx);
			}
		}
	}
	cout << res;
	return 0;
}

//一个游戏占据一个时间段
//截止时间之前没完成，扣钱
//
//优先完成扣钱多的游戏
//标记数组，标记这个时间点有没有被用
//
//5 截止时间，
//3 4   优先选择 4  剩下： 3 4 5 6 7 8 9
//当前选择时间 3 ， 4 5 6 7 8 9

#include <bits/stdc++.h>
using namespace std;
priority_queue<int>q;
const int N = 505;
struct node {
	int t, v;
} a[N];

bool cmp(node x,  node y) {
	return x.t > y.t;
}

int main() {
	int n, m;
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].t;
	for (int i = 1; i <= n; i++)
		cin >> a[i].v;
	sort(a + 1, a + 1 + n, cmp);
	int tmp = 1;
	for (int i = n; i >= 1; i --) {
		// tmp 物品必须在 1 - i 之间完成
		while (a[tmp].t >= i) {
			q.push(a[tmp].v);
			tmp ++;
		}
		// 在必须是 1-i 之前完成的物品中选择一个最大价值的完成
		if (!q.empty())  // 优先队列， 选择价值最高的完成
			q.pop();
	}
	int ans = m;
	while (!q.empty()) {  // 剩下在 队列中的就是不能完成的
		ans -= q.top();
		q.pop();
	}
	cout << ans;
	return 0;
}

//产品，需要在 A 机器加工，  然后在 B 机器加工
//求最短的加工时间，
//
//ai 代表 第 i 个物品在 机器A 上的时间
//bi 代表 第 i 个物品在 机器 B 上的时间
//1. ai<bi 的为一个组别
//	按照  ai 从小到大的顺序，依次加工
//2. ai>=bi 的为一个组别
//	按照 bi 从大到小的顺序， 依次加工
#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;
}

int n;
node a[N], b[N]; // a 数组存储 ai< bi 的 ， b ai>= bi 的
int la, lb;

int 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; // b 机器上的时间
		if (t[i] < tmp) {
			++la;
			a[la].a = t[i];
			a[la].b = tmp;
			a[la].id = i;
		} else {
			++lb;
			b[lb].a = t[i];
			b[lb].b = tmp;
			b[lb].id = i;
		}
	}
	sort(a + 1, a + 1 + la, cmp1);
	sort(b + 1, b + 1 + lb, cmp2);
	vector<int> ans;
	// ta 代表上一个物品用 a 机器的结束时间
	// tb 代表上一个物品用 b 机器的结束时间
	int ta = 0, tb = 0;
	for (int i = 1; i <= la ; i++) {
		ta += a[i].a;
		// 用 b 机器之前，保证了当前物品已经用完 a 机器 且 当前没有再用 B  机器
		tb = max(ta, tb) + a[i].b;
		ans.push_back(a[i].id);
	}

	for (int i = 1; i <= lb; i++) {
		ta += b[i].a;
		tb = max(ta, tb) + b[i].b;
		ans.push_back(b[i].id);
	}
	cout << tb << endl;
	for (auto t : ans)
		cout << t << " ";
	return 0;
}

//按照区间末尾排序 从小到大排序
//种树的时候，优先种区间末尾的树

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
struct node {
	int b, e, t;
	bool operator <(const node a)const {
		return e < a.e;
	}
};
int n, m;
node a[N];
int res;
bool vis[N]; // 标记某个位置有没有种树

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> a[i].b >> a[i].e >> a[i].t;
	sort(a + 1, a + 1 + m);
	// 依次处理每一个区间
	for (int i = 1; i <= m; i++) {
		int l = a[i].b, r = a[i].e;
		int t = a[i].t; // 当前区间需要种的树的数量
		for (int j = l ; j <= r && t ; j++) {
			if (vis[j])  // 代表 j 位置有 树
				t--;
		}
		// 剩下 t 棵树需要种
		for (int j = r ; t ; j--) { // 倒着种树
			if (vis[j] == 0) {
				vis[j] = 1;  // 标记当前位置种树了
				t--;
				res++;
			}
		}
	}
	cout << res;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 10;
int n, w;
int a[N];
int res;

int main() {
	cin >> w >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	int l = 1, r = n;
	while (l <= r) {
		if (a[l] + a[r] <= w)
			res++, l++, r--;
		else
			r--, res++;
	}
	cout << res;
	return 0;
}

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

struct node {
	int l, r;
	bool operator <(const node a)const {
		if (r != a.r)
			return r < a.r;  // 右边界从小到大排序
		return l < a.l;
	}
};
int n, res;
node a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].l >> a[i].r;
	sort(a + 1, a + 1 + n);
	res = 1;
	int last = a[1].r;  // 记录上一个比赛的结束位置
	// 遍历所有的比赛
	for (int i = 2; i <= n; i++) {
		// 判断当前比赛能不能参加
		if (a[i].l >= last)
			last = a[i].r, res++;
	}
	cout << res;
	return 0;
}

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

// 自定义的数据类型
// 数据类型的名字叫做  node，
// 属性是  time  id
struct node {
	int time, id;
	// 重载比较运算符
	// 如果时间不相等，就时间从小到大
	// 时间相等， 就按照 id 从小到大
	bool operator <(const node a) const {
		if (time != a.time)
			return time < a.time;
		return id < a.id;
	}
};
node a[N];  // 定义了一个结构体数组
int n;
long long res;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].time;
		a[i].id = i;
	}
	// 从小到大排序
	sort(a + 1, a + 1 + n);
	// 贪心策略： 按照接水时间从小到大排序，
	for (int i = 1; i <= n; i++) {
		cout << a[i].id << " ";
		res += 1LL * a[i].time * (n - i);
	}
	printf("\n%.2lf", res * 1.0 / n );
	return 0;
}

/*
by kivi 2026.2.22 智??冲浪 ?根堆做法
*/
#include <bits/stdc++.h>
using namespace std;

int main() {
	int m, n;
	cin >> m >> n;
	vector<pair<int, int>> games;
	int total_w = 0;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		games.push_back({t, 0});
	}
	for (int i = 0; i < n; i++) {
		cin >> games[i].second;
		total_w += games[i].second;
	}
//根据结束时间为主关键字从?到?，价值从?到?排序
	sort(games.begin(), games.end(), [](const auto & a, const auto & b) {
		if (a.first != b.first)
			return a.first < b.first;
		return a.second > b.second;
	});
//?根堆?来维护带截?时间的作业调度
	priority_queue<int, vector<int>, greater<int>> heap;
	int sum = 0;
	for (auto &game : games) {
		int t = game.first;
		int w = game.second;
//如果堆的数量?于截?时间，那么安排该游戏，并记?堆
		if (heap.size() < t) {
			heap.push(w);
			sum += w;
//如果之前已经安排的游戏数量达到t了，并且新的游戏能带来更好的收益
//弹出堆顶最?价值的游戏（贪?思想的体现）
		} else if (heap.size() == t && w > heap.top()) {
			sum -= heap.top();
			heap.pop();
			heap.push(w);
			sum += w;
		}
	}

	cout << m - (total_w - sum) << endl;
	return 0;
}