列表

详情

NC222483. [USACODec2020B]StuckinaRut

描述

Farmer John has recently expanded the size of his farm, so from the perspective of his cows it is effectively now infinite in size! The cows think of the grazing area of the farm as an infinite 2D grid of square "cells", each filled with delicious grass (think of each cell as a square in an infinite chessboard). Each of Farmer John's N cows (1≤N≤50) starts out in a different cell; some start facing north, and some start facing east.
Every hour, every cow either
Over time, each cow therefore leaves a barren "rut" of empty cells behind her.

If two cows move onto the same grassy cell in the same move, they share the cell and continue moving in their respective directions in the next hour.

Please determine the amount of grass eaten by each cow. Some cows never stop, and therefore eat an infinite amount of grass.

输入描述

The first line of input contains N. Each of the next N lines describes the starting location of a cow, in terms of a character that is either N (for north-facing) or E (for east-facing) and two nonnegative integers x and y (0≤x≤109, 0≤y≤109) giving the coordinates of a cell. All x-coordinates are distinct from each-other, and similarly for the y-coordinates.
To be as clear as possible regarding directions and coordinates, if a cow is in cell (x,y) and moves north, she ends up in cell (x,y+1). If she instead had moved east, she would end up in cell (x+1,y).

输出描述

Print N lines of output. Line i in the output should describe the number of cells worth of grass that the ith cow in the input eats. If a cow eats an infinite amount of grass, output "Infinity" for that cow.

示例1

输入: 

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1

输出: 

5
3
Infinity
Infinity
2
5

说明:

In test cases 2-5, all coordinates are at most 100.
In test cases 6-10, there are no additional constraints.
Problem credits: Brian Dean

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 3ms, 内存消耗: 436K, 提交时间: 2022-05-12 17:47:49 

// USACO 2020 Dec B. Stuck in a Rut
#include <bits/stdc++.h>
using namespace std;
struct Point {
  int x, y, id;
  bool operator<(const Point &p) const { return x < p.x; }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N;
  cin >> N;
  vector<Point> n_cows, e_cows;
  for (int i = 0, x, y; i < N; i++) {
    string dir;
    cin >> dir >> x >> y;
    (dir == "N" ? n_cows : e_cows).push_back({x, y, i});
  }
  sort(n_cows.begin(), n_cows.end());  // 按x排序
  sort(e_cows.begin(), e_cows.end(),
       [](Point &a, Point &b) { return a.y < b.y; });  // 按y排序
  vector<int> stop(N, -1);
  for (const Point &nc : n_cows)
    for (const Point &ec : e_cows) {
      int nd = ec.y - nc.y, ed = nc.x - ec.x;
      if (ed > 0 && nd > 0) {
        if (nd < ed && stop[ec.id] == -1)
          stop[ec.id] = ed;
        else if (ed < nd && stop[ec.id] == -1) {
          stop[nc.id] = nd;
          break;
        }
      }
    }
  for (int i = 0; i < N; i++) {
    if (stop[i] == -1)
      cout << "Infinity" << '\n';
    else
      cout << stop[i] << '\n';
  }
}

上一题

© 2024 nowcoder.com