首页 > 代码库 > poj1083,基本互斥问题

poj1083,基本互斥问题

题意:南北两侧各有200个房间,两侧房间之间有一个走廊

  现在需要把桌子从这400个房间之中搬进搬出,每一张桌子需要10分钟时间,如果走廊因为有桌子搬运而占用,则需等待,求共需多少时间(分钟)将桌子搬完

分析:由于走廊跨越200个房间,设置数组大小为200的数组,如从x出发搬到y,则把x到y的走廊全部+10,最后求该数组最大值,便是结果

原因:若从x出发到y,中间有桌子也需要搬运,则冲突的路段势必会耽误10分钟时间,耽误时间的最大值便是结果(只要不冲突,同一时间可以搬运多张桌子)

import java.util.Arrays;
import java.util.Scanner;

public class Main1083 {
    
    public static int getMax(int[] a){
        
        int max = 0;
        for(int i=0;i<a.length;i++){
            if(a[i]>max){
                max = a[i];
            }
        }
        return max;
        
    }

    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t-->0){
            int[] corridor = new int[200];
            int n = scanner.nextInt();
            for(int i=0;i<n;i++){
                int x,y;
                int start,end;
                x = scanner.nextInt();
                y = scanner.nextInt();
                start = ((x > y? y : x)-1)/2;
                end = ((x < y? y : x)-1)/2;
                for(int j=start;j<=end;j++){
                    corridor[j] += 10;
                }
            }
            System.out.println(getMax(corridor));
        }
        
    }

}

 

poj1083,基本互斥问题