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

poj1083，基本互斥问题

2024-10-18 04:13:02   213人阅读

题意：南北两侧各有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，基本互斥问题


联系
我们