ABC005题的答案[Java]

2 年 ago
宇, 华
2 minutes

首先

不知不觉间，我已经解答完这个比赛的所有问题了，所以打算把它发布出来。

那么，让我们开始看吧。

A – 做美味的章鱼烧的方法

请问问题是什么？

我们只需要求出x是y的几倍即可。
简单地进行除法运算即可，结果将会是向下取整的商。

import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    //x、yの受け取り
    int x = sc.nextInt();
    int y = sc.nextInt();

    //切り捨て除算
    System.out.println(y/x);
  }
}

B – 如何享用美味的章鱼烧

问题见下文。

根据问题的要求，我们需要总结出输出$T$的最小值，因此我们计算了它。

import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    //Nの受け取り
    int N = sc.nextInt();
    int min = 1000; //最小値を求める用(大きければ初期値は何でも良い)

    //最小値を探す
    for(int i=0;i<N;i++){
      int temp = sc.nextInt();
      if(min>temp)
        min = temp;
    }

    //答えの出力
    System.out.println(min);
  }
}

C – 可口的章鱼烧销售方式

这里是问题陈述。

我在处理时考虑到以下几点：
– 对于每个客户，提供的章鱼烧应该是在T秒内制作的最早的，这样才更有利。
– 基于上述思考，可以按照先来先服务的原则来进行处理。
因此，我将A和B分别放入ArrayDeque中，并只查看队列的头部元素，以便进行最优的处理。

import java.util.Scanner;
import java.util.ArrayDeque;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    //T、Nの受け取り
    int T = sc.nextInt();
    int N = sc.nextInt();

    //AをArrayDequeに
    ArrayDeque<Integer> A = new ArrayDeque<>();
    for(int i=0;i<N;i++)
      A.add(sc.nextInt());

    //Mの受け取り
    int M = sc.nextInt();

    //BをArrayDequeに
    ArrayDeque<Integer> B = new ArrayDeque<>();
    for(int i=0;i<M;i++)
      B.add(sc.nextInt());

    //お客さんに配っていく
    while(B.size()>0){

      //今来たお客さん
      int order = B.pollFirst();

      //条件を満たすたこ焼きが見つかるまで取り出す
      int takoyaki = A.isEmpty()?order+1:A.pollFirst();
      while(takoyaki+T<order)
        takoyaki = A.isEmpty()?order+1:A.pollFirst();

      //条件を満たすものが無かったら終わり
      if(takoyaki>order){
        System.out.println("no");
        return;
      }
    }

    //全員に提供できたらyes
    System.out.println("yes");
  }
}

D – 香脆美味的章鱼烧制作方法

问题文在这里。

由于约束条件较小，我们事先计算了关于D的二维累积和，并通过对每个店员可烤香肠的上限进行全搜索，从而求得矩形和的最大值。

import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    //Nの受け取り
    int N = sc.nextInt();

    //二次元累積和の構築
    int[][] sumD = new int[N+1][N+1];
    for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++){
        sumD[i][j] = sumD[i-1][j]+sumD[i][j-1]-sumD[i-1][j-1]+sc.nextInt();
      }
    }

    //Qの受け取り
    int Q = sc.nextInt();
    while(Q-->0){

      //Pの受け取り
      int P = sc.nextInt();

      //最大値の全探索
      int max = 0;

      //縦方向の幅を決め打つ
      for(int x=1;x<=N;x++){

        //横幅が求まる
        int y = Math.min(N,P/x);

        //右下の縦方向の座標
        for(int i=x;i<=N;i++){

          //右下の横方向の座標
          for(int j=y;j<=N;j++){
            max = Math.max(max,sumD[i][j]-sumD[i-x][j]-sumD[i][j-y]+sumD[i-x][j-y]);
          }
        }
      }

      //最大値のしゅつりょく
      System.out.println(max);
    }
  }
}
bannerAds