AtCoder Beginner Contest 334

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;
	}

}