CF981B Businessmen Problems 题解

Content

有一个长度为 \(n\) 的序列和长度为 \(m\) 的序列,两个序列中的元素都有一个编号 \(num\) 和一个值 \(val\),且同一个序列的元素之间的编号互不相同。现在从这两个序列中选取一些元素,要求编号不能重复,求能够取到的最大价值。

数据范围:\(1\leqslant n,m\leqslant 10^5,1\leqslant num,val\leqslant 10^9\)。

Solution

我们可以开个 \(vis\) 数组来判断是否之前取过,同时它还起到储存当前编号的元素的价值。但是范围太大怎么办?用 \(\texttt{map}\) 呗,直接映射来实现就好。

如果出现了两个编号相同的元素,怎么办?取相同编号之间价值的较大值就好。

Code

int n, m, a[100007], x, b[100007], y;
map<int, int> vis;
ll ans;

int main() {
	getint(n);
	_for(i, 1, n) {
		getint(a[i]), getint(x);
		vis[a[i]] = x;
		ans += x;
	}
	getint(m);
	_for(i, 1, m) {
		getint(b[i]), getint(y);
		if(vis[b[i]] < y) {
			ans += (y - vis[b[i]]);
			vis[b[i]] = y;
		}
	}
	writell(ans);
	return 0;
}
上一篇:POJ2151 Check the difficulty of problems


下一篇:rabbitmq_problems