Home » 国际竞赛 » Details

USACO 2021 December Contest, Silver Problem 1. Closest Cow Wins

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午2:32

USACO 2021 December Contest, Silver Problem 1. Closest Cow Wins

Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are $K$ grassy patches ( $1 \leq K \leq 2 \cdot 10^{5}$ ); the $i$ -th patch is located at position $p_{i}$ and has an associated tastiness value $t_{i}$ ( $0 \leq t_{i} \leq 10^{9}$ ). Farmer John's nemesis, Farmer Nhoj, has already situated his $M$ cows ( $1 \leq M \leq 2 \cdot 10^{5}$ ) at locations $f_{1} \dots f_{M}$ . All $K + M$ of these locations are distinct integers in the range $[0, 10^{9}]$ .

Farmer John needs to pick $N$ ( $1 \leq N \leq 2 \cdot 10^{5}$ ) locations (not necessarily integers) for his cows to be located. These must be distinct from those already occupied by the cows of Farmer Nhoj, but it is possible for Farmer John to place his cows at the same locations as grassy patches.

Whichever farmer owns a cow closest to a grassy patch can claim ownership of that patch. If there are two cows from rival farmers equally close to the patch, then Farmer Nhoj claims the patch.

Given the locations of Farmer Nhoj's cows and the locations and tastiness values of the grassy patches, determine the maximum total tastiness Farmer John's cows can claim if optimally positioned.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $K$ , $M$ , and $N$ .The next $K$ lines each contain two space-separated integers $p_{i}$ and $t_{i}$ .

The next $M$ lines each contain a single integer $f_{i}$ .

OUTPUT FORMAT (print output to the terminal / stdout):

An integer denoting the maximum total tastiness. Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., "long long"s in C or C++).

SAMPLE INPUT:

SAMPLE OUTPUT:

If Farmer John places cows at positions $11.5$ and $8$ then he can claim a total tastiness of $10 + 12 + 14 = 36$ .

Problem credits: Brian Dean

USACO 2021 December Contest, Silver Problem 1. Closest Cow Wins 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Farmer Nhoj's cows partition the number line into $M + 1$ intervals. The general idea is to find the answers for each of these intervals independently, and then combine them.

Firstly, note that John can claim the total tastiness of the leftmost interval with a single cow. Similar reasoning holds for the rightmost interval. Every other of the $M - 1$ intervals has one of Nhoj's cows at both of its endpoints, so one of John's cows might not be enough to claim all of the tastinesses within it. But placing two cows will definitely be enough (one just to the right of the left endpoint of the interval, and another just to the left of the right endpoint of the interval).

Assume all the patches and cows are sorted in increasing order of position, and consider the interval $(f_{x - 1}, f_{x})$ . Probably the trickiest part of the solution involves computing the maximum tastiness John can claim if he places only one cow in this interval. If John places a cow at $q \in (f_{x - 1}, f_{x})$ , he claims the tastinesses of all patches with positions in the range $(\frac{f_{x - 1} + q}{2}, \frac{f_{x} + q}{2})$ . Note that the length of this range ("window") is equal to $\frac{f_{x} - f_{x - 1}}{2}$ regardless of $q$ . We can slide this constant-length window from left to right and keep track of how the sum of tastinesses changes as patches enter and exit this window. The one-cow answer for this interval will equal the maximum sliding window sum that we ever encounter.

Now that we've computed the one-cow and two-cow answers for every interval, it remains to combine these to get the answer to the original problem. If John was restricted to placing at most one cow in every interval, then we could create a list of all the one-cow answers, sort it in decreasing order, and sum its first $N$ elements. It turns out that a slight modification of this strategy works when we allow John to place up to two cows in every interval: add the quantity $(two-cow answer - one-cow answer)$ for each interval to the list before sorting it (if there are ties, put quantities of the form $one-cow answer$ before quantities of the form $(two-cow answer - one-cow answer)$ ).

The reason these works is because $2 \cdot (one-cow answer) \geq (two-cow answer)$ for any interval; in other words, adding a second cow to an interval can't increase the total tastiness more than adding the first cow did. This implies that if a prefix of the list contains the quantity $(two-cow answer - one-cow answer)$ for an interval, it will also contain the quantity $one-cow answer$ for that same interval.

My code (with a single vector for both the patches and Nhoj's cows):

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int K, M, N;
	cin >> K >> M >> N;
	vector<pair<int, int>> patches(K + M); // patches and Nhoj's cows
	for (int i = 0; i < K; ++i)
		cin >> patches[i].first >> patches[i].second;
	for (int i = K; i < K + M; ++i) {
		cin >> patches[i].first;
		patches[i].second = -1;
	}
	sort(begin(patches), end(patches));
	vector<uint64_t> increases;
	int last_i = -1;
	uint64_t sum_range = 0;
	for (int i = 0; i < (int)patches.size(); ++i) {
		if (patches[i].second == -1) {
			if (last_i == -1) { // try placing to left of Nhoj's leftmost cow
				increases.push_back(sum_range);
			} else {
				uint64_t cur_ans_1 = 0;	 // current sum of window
				uint64_t best_ans_1 = 0; // best sum over all windows
				for (int j = last_i + 1, r = last_i; j < i; ++j) {
					// assume j is the leftmost patch in the window
					while (r + 1 < i &&
						   (patches[r + 1].first - patches[j].first) * 2 <
							   patches[i].first - patches[last_i].first) {
						cur_ans_1 += patches[++r].second;
					}
					// window sum is now sum(tastinesses(j..r))
					best_ans_1 = max(best_ans_1, cur_ans_1);
					cur_ans_1 -= patches[j].second;
				}
				assert(2 * best_ans_1 >= sum_range);
				// answer for one cow
				increases.push_back(best_ans_1);
				// answer for two cows - answer for one cow
				increases.push_back(sum_range - best_ans_1);
			}
			last_i = i;
			sum_range = 0;
		} else {
			sum_range += patches[i].second;
		}
	}
	// try placing to right of Nhoj's rightmost cow
	increases.push_back(sum_range);
	// sort in decreasing order
	sort(rbegin(increases), rend(increases));
	increases.resize(N);
	uint64_t ans = 0;
	for (auto val : increases)
		ans += val;
	cout << ans << "\n";
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
 
public class ClosestCowWins {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int k = Integer.parseInt(tokenizer.nextToken());
        int m = Integer.parseInt(tokenizer.nextToken());
        int n = Integer.parseInt(tokenizer.nextToken());
        Patch[] patches = new Patch[k];
        for (int j = 0; j < k; j++) {
            tokenizer = new StringTokenizer(in.readLine());
            int location = Integer.parseInt(tokenizer.nextToken());
            long tastiness = Long.parseLong(tokenizer.nextToken());
            patches[j] = new Patch(location, tastiness);
        }
        Arrays.sort(patches);
        long[] tastinessSums = new long[k + 1];
        for (int j = 0; j < k; j++) {
            tastinessSums[j + 1] = tastinessSums[j] + patches[j].tastiness;
        }
        Integer[] nhojCows = new Integer[m];
        for (int j = 0; j < m; j++) {
            nhojCows[j] = Integer.parseInt(in.readLine());
        }
        Arrays.sort(nhojCows);
        TreeMap<Integer, Integer> nhojCowsTreeMap = new TreeMap<>();
        for (int j = 0; j < m; j++) {
            nhojCowsTreeMap.put(nhojCows[j], j);
        }
        TreeMap<Integer, Integer> patchTreeMap = new TreeMap<>();
        for (int j = 0; j < k; j++) {
            patchTreeMap.put(patches[j].location, j);
        }
        long[][] valueAdded = new long[3][m + 1];
        for (int j = 0; j < k; j++) {
            Map.Entry<Integer, Integer> nextNhojCowEntry = nhojCowsTreeMap.ceilingEntry(patches[j].location);
            int nextNhojCow = nextNhojCowEntry == null ? m : nextNhojCowEntry.getValue();
            valueAdded[2][nextNhojCow] += patches[j].tastiness;
            if (nextNhojCow == 0 || nextNhojCow == m) {
                valueAdded[1][nextNhojCow] += patches[j].tastiness;
            } else {
                int johnCowLocation = Math.min(nhojCows[nextNhojCow], (2 * patches[j].location) - nhojCows[nextNhojCow - 1]);
                int extent = (johnCowLocation + nhojCows[nextNhojCow] + 1) / 2;
                int farthestPatch = patchTreeMap.lowerEntry(extent).getValue();
                valueAdded[1][nextNhojCow] = Math.max(valueAdded[1][nextNhojCow], tastinessSums[farthestPatch + 1] - tastinessSums[j]);
            }
        }
        Long[] valueAddedOverall = new Long[2 * (m + 1)];
        for (int j = 0; j <= m; j++) {
            valueAddedOverall[2 * j] = valueAdded[1][j];
            valueAddedOverall[(2 * j) + 1] = valueAdded[2][j] - valueAdded[1][j];
        }
        Arrays.sort(valueAddedOverall);
        long answer = 0;
        for (int j = Math.max(0, valueAddedOverall.length - n); j < valueAddedOverall.length; j++) {
            answer += valueAddedOverall[j];
        }
        System.out.println(answer);
    }
 
    public static class Patch implements Comparable<Patch> {
        final int location;
        final long tastiness;
 
        public Patch(int location, long tastiness) {
            this.location = location;
            this.tastiness = tastiness;
        }
 
        @Override
        public int compareTo(Patch other) {
            return location - other.location;
        }
    }
}

Bonus: It would still be possible to solve this question even if the condition $2 \cdot (one-cow answer) \geq (two-cow answer)$ did not hold (see this problem).

[/hide]