夏晓光(loveJY)的博客

IOI2020集训队作业

没什么好说的,贪心啊

• 有 $k$ 个正整数 $a_{1\dots k}$。
• 有 $n$ 个操作，每个操作给定正整数 $b$，有三种可能：将 $a_i$ 赋值为 $b$，将 $a_i$ 加上 $b$，将 $a_i$ 乘以 $b$。
• 你可以从 $n$ 个操作中选择最多 $m$ 个操作，并按照一定顺序执行。
• 你的目标是最大化 $\prod_{i=1}^k a_i$​ 的值。
• $k,n \le 10^5$。

然后你会发现这个问题一定是贪心,因为如果是DP我们连这些东西乘起来的答案都记不下来

那就分析三种操作吧

操作1.乘

相当于答案变成了$b*\prod_{i=1}^{n}a_i$

也就是说乘对于任何都是一样的,我们只需要把它按乘数大小排序就行了

注意乘法有一个性质,就是可以任意先后的执行,因为原题还要我们自定顺序,这个真的恶心吗?

操作2.加

加...好像可以变成乘法?

比如把x加上y就相当于x乘上$\frac{x+y}{x}$

然后好像就可以排序和乘法一样了?不过这个成立的前提是我们每次加法只从大的开始加起...

感性理解一下好像我们也应该从大的还是加喵?所以我们一定从大到小加啊

操作3.赋值

这个显然不能像之前莽,要分析一下

首先一个数最多赋值一次,因为如果不的话相当于我们白浪费了一次操作,搜索一可以先去掉劣的...

然后经过初步筛选之后就可以看做一个加法?加上了y-x,就可以放进操作2中一起做了

这个为啥是对的啊?有个本题最关键的结论

我们三个操作一定是按照先赋值再加再乘的顺序来的

因为赋值一定只放在一开始最优,加法一定要被乘法影响最大最优

唔母,这样我们就可以看做如果赋值了就是放在第一个,又因为没有两个赋值操作,所以一定可以

其他的由乘法可任意交换la

code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;
int n, m, k, tot1, tot2, tot3, cnt;
ll s[MAXN];
struct node {
	int opt, id, x;
	ll v, w;//w为分母
} m1[MAXN], m2[MAXN], m3[MAXN], ans[MAXN];

namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}

	inline int read() {
		int x = 0, f = 1;
		register char s = nc();
		for(; !isdigit(s); s = nc())if(s == '-')f = -1;
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x * f;
	}
}
using namespace fastIO;

inline bool cmp1(node a, node b) {
	return (a.x != b.x) ? (a.x < b.x) : (a.v < b.v);
	//1
}
inline bool cmp2(node a, node b) {
	return (a.x != b.x) ? (a.x < b.x) : (a.v > b.v);
	//贪心
}
inline bool cmp3(node a, node b) {
	return a.opt < b.opt;
	//qwq
}
inline bool cmp4(node a, node b) {
	return a.v * b.w > a.w * b.v;
	//分数叉积判
}

void pre() {
	n = read();
	m = read();
	k = read();
	for(register int i = 1; i <= n; ++i)s[i] = read();
	for(register int i = 1; i <= m; ++i) {
		int a = read(), b = read(), c = read();
		if(a == 1 && c > s[b])m1[++tot1] = (node) {
			1, i, b, c, 1
		};//改了就不
		else if(a == 2)m2[++tot2] = (node) {
			2, i, b, c, 1
		};
		else if(a == 3) {
			m3[++tot3] = (node) {
				3, i, b, c, 1
			};
		}
	}
}

void build() {
	sort(m1 + 1, m1 + tot1 + 1, cmp1);
	int tmp = 0;
	for(register int i = 1; i <= tot1; ++i) {
		if(m1[i].x != m1[i + 1].x)m1[++tmp] = m1[i];//赋值操作留最大
	}
	tot1 = tmp;
	for(register int i = 1; i <= tot1; ++i) {
		m1[i].v = m1[i].v - s[m1[i].x], m2[++tot2] = m1[i];//赋值变成加法
	}
	//tot1 = tmp;
	sort(m2 + 1, m2 + tot2 + 1, cmp2);
	ll sum = 0;
	for(register int i = 1; i <= tot2; ++i) {
		if(m2[i].x != m2[i - 1].x)sum = s[m2[i].x];
		m2[i].w = sum, sum += m2[i].v;
	}

	for(register int i = 1; i <= tot3; ++i)m3[i].v--;
	for(register int i = 1; i <= tot2; ++i)m3[++tot3] = m2[i];
}

inline void work() {
	sort(m3 + 1, m3 + tot3 + 1, cmp4);
	int tmp = min(tot3, k);
	for(register int i = 1; i <= tmp; ++i)ans[++cnt] = m3[i];
	printf("%d\n", cnt);
	sort(ans + 1, ans + cnt + 1, cmp3);
	for(register int i = 1; i <= cnt; ++i)printf("%d ", ans[i].id);
	printf("\n");
}

int main() {
	//freopen("test.in","r",stdin);
	pre();
	build();
	work();
	return 0;
}