USACO 2015 US Open, Bronze Problem 3. Trapped in the Haybales (Bronze)

原題下載

USACO2015OPEN-B3

答案

(Analysis by Nick Wu)

The?NN?hay bales define?N?1N?1?intervals that Bessie can be inside. Let's consider answering for a given interval, whether Bessie can escape if she starts inside that interval.

We can, in fact, ask a more general question - if Bessie is trapped between haybale?ii?and haybale?jj, can she escape? Clearly, if Bessie can break through haybale?ii, it is to her advantage to do so immediately - she then gains more distance and can possibly break through haybale?jj. However, if Bessie can break through neither haybale?ii?nor haybale?jj, then she is trapped.

We can then simulate this process as follows. Start by having Bessie be trapped between haybale?ii?and haybale?i+1i+1. While she still has a haybale to her left and a haybale to her right, see if she can break either one. Keep on breaking haybales until either she doesn't have one to her left or one to her right, or she can't break through either one. If she can't break through the haybales to her left and to her right, then take the distance of the original interval and add to that a running total. Repeat this simulation for all adjacent pairs of haybales.

Here is my Java code simulating this process.

import java.io.*;
import java.util.*;
public class trappedB {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("trapped.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("trapped.out")));
    int n = Integer.parseInt(br.readLine());
    Haybale[] bales = new Haybale[n];
    for(int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int size = Integer.parseInt(st.nextToken());
      int position = Integer.parseInt(st.nextToken());
      bales[i] = new Haybale(size, position);
    }
    // sort haybales by location
    Arrays.sort(bales);
    int ans = 0;
    for(int i = 0; i < n-1; i++) {
      int areaOfInterval = bales[i+1].position - bales[i].position;
      int leftmostBale = i;
      int rightmostBale = i+1;
      // while Bessie could still be trapped
      while(leftmostBale >= 0 && rightmostBale <= n-1) {
        boolean broke = false;
        int currDist = bales[rightmostBale].position - bales[leftmostBale].position;
        if(currDist > bales[leftmostBale].size) {
          leftmostBale--;
          broke = true;
        }
        if(currDist > bales[rightmostBale].size) {
          rightmostBale++;
          broke = true;
        }
        // Bessie couldn't break through either the left or the right bale, so stop
        if(!broke) {
          break;
        }
      }
      // Bessie couldn't break out
      if(leftmostBale >= 0 && rightmostBale <= n-1) {
        ans += areaOfInterval;
      }
    }
    pw.println(ans);
    pw.close();
  }
    
  static class Haybale implements Comparable<Haybale> {
    public int position, size;
    public Haybale(int sizeIn, int positionIn) {
      size = sizeIn;
      position = positionIn;
    }
    public int compareTo(Haybale h) {
      // this will sort haybales from left to right
      return position - h.position;
    }
  }
  
}

以上就是關于【USACO 2015 US Open, Bronze Problem 3. Trapped in the Haybales (Bronze)】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

2026理工科競賽“大洗牌”：線上考試終結、報名門檻收緊、晉級規則重塑...你準備好了嗎？