AtCoder Beginner Contest 334

2023-12-28 12:51:14

B - Christmas Trees

分析:

讨论三种情况

1) l<=a<=r

2)a<l

3)a>r

虽然简单,但是坑还是有一些的

例如2的策略是,[a,r]的树 - [a,l]的树,然后要注意 l 点有没有树,如果有树的话,刚刚的操作会把 l 位置的树也减去了,那ans要加1

3)也一样

1)就简单了,记得加上a点本身的树就行

void solve() {
	int a, m, l, r; cin >> a >> m >> l >> r;
	int ans = 0;
	if (a < l) {
		ans = (r - a) / m - (l - a) / m;
		if ((l - a) % m == 0) ans++;
	}
	else if (a > r) {
		ans = (a - l) / m - (a - r) / m;
		if ((a - r) % m == 0) ans++;
	}
	else {
		ans = (r - a) / m + (a - l) / m + 1;
	}

	cout << ans;
}

C - Socks 2

这题有点难,没想到前缀和结合后缀和运用。。。

分析:完整的袜子就不用动了,怪异程度是0。我们要把不完整的k只袜子组合成k/2双袜子。

先对k个袜子进行排序

1)当k是偶数,那么相邻的两只袜子组成一双是最优策略,这很容易证明

2)当k是奇数,那么就要有一只袜子不选,剩下的 k-1只袜子组对。

选哪一只呢?暴力枚举的时间复杂度是O(n2),显然会超时。

进一步分析可以知道,一定是选在奇数位置上的袜子,(选a[i],i是奇数),这个也不证明了,比较容易想。

到底要怎么样才能在O(n)得出答案呢?

假如第i只袜子不选,我们可以知道 i之前?和 i之后 的怪异程度之和就好了。

这个可以用前缀和pre+后缀和suf实现,存怪异程度的前缀和和后缀和

第i只袜子不选的总怪异程度 = pre[i-1] + suf[i+1]

ps:后缀和的用法要牢记,博主就是在这个知识点上犯糊涂了。

假如有n个数,装在数组a里,那么suf[i] = a[n]~a[i]的后缀和,

我理解成了suf[i] = a[n]~a[n-i]的后缀和,这是错误的。

int a[N], pre[N], suf[N];

void solve() {
	int n, k; cin >> n >> k;
	for (int i = 1; i <= k; i++) cin >> a[i];
	sort(a + 1, a + 1 + k);

	if (k % 2 == 0) {
		int ans = 0;
		for (int i = 2; i <= k; i += 2) {
			ans += a[i] - a[i - 1];
		}
		cout << ans;
	}

	else {
		for (int i = 2; i <= k; i += 2) {
			pre[i] = pre[i - 2] + (a[i] - a[i - 1]);
		}
		for (int i = k - 1; i >= 1; i-=2) {
			suf[i] = suf[i + 2] + (a[i + 1] - a[i]);
		}

		int ans = inf;
		for (int i = 1; i <= k; i += 2) {
			ans = min(ans, pre[i - 1] + suf[i + 1]);
		}
		cout << ans;
	}

}

D - Reindeer and Sleigh

这题代码量虽然大,但我觉得比C简单多了。

知识点:前缀和,双指针,哈希数组

分析:一眼看出要用前缀和,O(n2)的复杂度的暴力做法很容易想到,问题是怎么在O(n)的时间复杂度里完成查询。

创建结构体存q次的查询的值,还有其查询的顺序(也就是下标)。以val排升序。

然后双指针,一个指向pre一个指向node

对了,记得开一个哈希数组存答案,因为输出是按顺序输出的

int a[N], pre[N], ans[N];
struct Node {
	int val, index;
}node[N];

bool cmp(Node e1, Node e2) {
	return e1.val < e2.val;
}
void solve() {
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + 1 + n);

	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + a[i];
	}

	
	for (int i = 1; i <= q; i++) {
		cin >> node[i].val;
		node[i].index = i;
	}
	sort(node + 1, node + 1 + q, cmp);
	
 	pre[n + 1] = 1e18;
	int pn = 1, pp = 1;
	while (pn <= q) {
		if (node[pn].val < pre[pp]) {
			ans[node[pn].index] = pp - 1;
			pn++;
		}
		else {
			pp++;
			if (pp == n + 2) pp = n + 1;
		}
	}

	for (int i = 1; i <= q; i++) {
		//tans;
		cout << ans[i] << endl;
	}

}

文章来源:https://blog.csdn.net/clmm_/article/details/135265625
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。