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