百度-裁減網格紙百度-罪犯轉移

百度-裁減網格紙

題目描述

度度熊有一張網格紙，但是紙上有一些點過的點，每個點都在網格點上，若把網格看成一個坐标軸平行于網格線的坐标系的話，每個點可以用一對整數x，y來表示。度度熊必須沿着網格線畫一個正方形，使所有點在正方形的内部或者邊界。然後把這個正方形剪下來。問剪掉正方形的最小面積是多少。

輸入描述:

第一行一個數n(2≤n≤1000)表示點數，接下來每行一對整數xi,yi(－1e9<=xi,yi<=1e9)表示網格上的點

輸出描述:

一行輸出最小面積

輸入例子:

0 0

0 3

輸出例子:

解題思路：比較簡單的一道題，根據測試用例，隻需要判斷兩點之間水準/垂直方向的最大距離，即求最大最小x和y。然後比較出最大距離求平方，然後需要注意，當隻有一個點的時候實際上面積是1，而不是0。

import java.util.*;

public class Main{

    public static void main(String []args){
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            String line=scan.nextLine();
            int n=Integer.parseInt(line.trim());
            int xmin=;
            int xmax=;
            int ymin=;
            int ymax=;
            for(int i=;i<n;i++){
                line=scan.nextLine();
                String []lines=line.trim().split(" ");
                int tmp=Integer.parseInt(lines[]);
                xmin=tmp<xmin?tmp:xmin;
                xmax=tmp>xmax?tmp:xmax;
                tmp=Integer.parseInt(lines[]);
                ymin=tmp<ymin?tmp:ymin;
                ymax=tmp>ymax?tmp:ymax;
            }
            int max=(xmax-xmin)>(ymax-ymin)?xmax-xmin:ymax-ymin;
            if(max==&&n!=){
                System.out.println();
            }else{
                System.out.println(max*max);
            }
        }
    }

}

做了2天題目之後，對這個輸入輸出還算比較熟悉了~！。

百度-罪犯轉移

C市現在要轉移一批罪犯到D市，C市有n名罪犯，按照入獄時間有順序，另外每個罪犯有一個罪行值，值越大罪越重。現在為了友善管理，市長決定轉移入獄時間連續的c名犯人，同時要求轉移犯人的罪行值之和不超過t，問有多少種選擇的方式？

輸入描述:

第一行資料三個整數:n，t，c(1≤n≤2e5,0≤t≤1e9,1≤c≤n)，第二行按入獄時間給出每個犯人的罪行值ai(0≤ai≤1e9)

輸出描述:

一行輸出答案。

輸入例子:

3 100 2

1 2 3

輸出例子:

解題思路：類似計算流的方式吧？就是不回頭的計算，避免重複工作。在計算c個罪行值和之後，每次減去第一個，增加後一個，滿足條件就counter++。更好的應該是判斷完目前情況減去最老的一個，然後讀新資料時候再增加進行判斷，這時候保持隻有C個罪犯在記憶體中。

import java.util.*;

public class Main{

    public static void main(String []args) throws Exception{
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            String line=scan.nextLine();
            String[] lines=line.trim().split(" ");
            int n=Integer.parseInt(lines[]);
            int t=Integer.parseInt(lines[]);
            int c=Integer.parseInt(lines[]);

            int []crm=new int[n];
            line=scan.nextLine();
            lines=line.trim().split(" ");
            for(int i=;i<n;i++){
                crm[i]=Integer.parseInt(lines[i]);
            }

            int sum=;
            int counter=;
            for(int i=;i<c;i++){
                sum+=crm[i];
            }
            if(sum<=t){
                counter++;
            } 
            for(int i=c;i<n;i++){
                sum-=crm[i-c];
                sum+=crm[i];
                if(sum<=t){
                    counter++;
                }
            }
            System.out.println(counter);
        }
    }
}

感覺不錯~今天30分鐘就做完2個題目~加油！

百度-裁減網格紙百度-罪犯轉移