头像

peilin




离线:8个月前



peilin
9个月前


import java.util.*;

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

        int n = scanner.nextInt();
        int m = scanner.nextInt();

        int[] sums = new int[n+1];
        sums[0] = 0;
        for(int i = 1; i <= n; i++) {
            sums[i] = sums[i-1] + scanner.nextInt();
        }

        Deque<Integer> deque = new ArrayDeque<>();
        deque.offerLast(0);
        int ans = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if(deque.isEmpty()) deque.offerLast(i);
            else {
                if(i - deque.peekFirst() > m) {
                    deque.removeFirst();
                }
                ans = Math.max(ans, sums[i] - sums[deque.peekFirst()]);
                while(!deque.isEmpty() &&sums[deque.peekLast()] >= sums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(i);
            }
        }

        System.out.println(ans);
    }
}




peilin
9个月前
import java.util.*;

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

        //the number of teams
        int t = scanner.nextInt();
        int k = 1;

        while (t != 0) {
            System.out.format("Scenario #%d%n", k);

            int[] personToTeamId = new int[1000000];
            for(int i = 1; i <= t; i++) {
                int size = scanner.nextInt();
                while(size-- > 0) {
                    personToTeamId[scanner.nextInt()] = i;
                }
            }

            List<Queue<Integer>> queuesList = new ArrayList<>(t);
            for(int i = 0; i < t; i++) {
                queuesList.add(new LinkedList<>());
            }

            Queue<Integer> teams = new LinkedList<>();

            String instruction = scanner.next();
            while(!instruction.equals("STOP")) {
                if(instruction.equals("ENQUEUE")) {
                    int personId = scanner.nextInt();
                    int teamId = personToTeamId[personId];
                    Queue<Integer> queue = queuesList.get(teamId - 1);

                    if(queue.isEmpty()) {
                        queue.offer(personId);
                        teams.offer(teamId);
                    } else {
                        queue.offer(personId);
                    }
                } else {
                    int teamId = teams.peek();
                    Queue<Integer> queue = queuesList.get(teamId - 1);
                    System.out.println(queue.poll());

                    if(queue.isEmpty()) teams.poll();
                }

                instruction = scanner.next();
            }

            System.out.println();
            t = scanner.nextInt();
            k++;
        }
    }
}



peilin
9个月前

Java 代码

import java.util.*;

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

        int n = scanner.nextInt();

        while(n != 0) {
            int[] height = new int[n+1];
            for(int i = 0; i < n; i++) {
                height[i] = scanner.nextInt();
            }
            height[n] = 0;

            Deque<Rectangle> stack = new ArrayDeque<>();
            stack.push(new Rectangle(height[0], 1));
            long ans = 0;

            for(int i = 1; i <= n; i++) {
                if(stack.peek().h < height[i]) stack.push(new Rectangle(height[i], 1));
                else {
                    int width = 0;
                    while(!stack.isEmpty() && stack.peek().h >= height[i]) {
                        Rectangle rectangle = stack.pop();
                        width += rectangle.w;
                        ans = Math.max(ans, (long) rectangle.h * width);
                    }

                    stack.push( new Rectangle(height[i], width + 1) );
                }
            }

            System.out.println(ans);
            n = scanner.nextInt();
        }
    }
}

class Rectangle {
    int h, w;

    public Rectangle(int h, int w) {
        this.h = h;
        this.w = w;
    }
}



peilin
9个月前
import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int) in.nval;
            Deque<Integer> numStackLeft = new ArrayDeque<>(n);
            Deque<Integer> numStackRight = new ArrayDeque<>(n);
            int[] sums = new int[n + 1];
            int[] sumsMax = new int[n + 1];
            sums[0] = 0;
            sumsMax[0] = Integer.MIN_VALUE;

            while (n-- > 0) {
                in.nextToken();
                String c = in.sval;
                switch (c) {
                    case "I":
                        in.nextToken();
                        numStackLeft.push((int) in.nval);
                        sums[numStackLeft.size()] = sums[numStackLeft.size() - 1] + numStackLeft.peek();
                        sumsMax[numStackLeft.size()] = Math.max(sumsMax[numStackLeft.size() - 1], sums[numStackLeft.size()]);
                        break;
                    case "D":
                        if (!numStackLeft.isEmpty()) {
                            numStackLeft.pop();
                        }
                        break;
                    case "L":
                        if (!numStackLeft.isEmpty()) {
                            numStackRight.push(numStackLeft.pop());
                        }
                        break;
                    case "R":
                        if (!numStackRight.isEmpty()) {
                            numStackLeft.push(numStackRight.pop());
                            sums[numStackLeft.size()] = sums[numStackLeft.size() - 1] + numStackLeft.peek();
                            sumsMax[numStackLeft.size()] = Math.max(sumsMax[numStackLeft.size() - 1], sums[numStackLeft.size()]);

                        }
                        break;
                    case "Q":
                        in.nextToken();
                        int k = (int) in.nval;
                        out.println(sumsMax[k]);
                        break;
                }
            }
            out.flush();
        }
    }
}



peilin
9个月前
class MinStack {
    private Node head;

    /** initialize your data structure here. */
    public MinStack() {
        head = null;
    }

    public void push(int x) {
        if(head == null) {
            head = new Node(x, x, null);
        } else {
            head = new Node(x, Math.min(x, head.min), head);
        }
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        return head.value;
    }

    public int getMin() {
        return head.min;
    }

    private class Node {
        int value;
        int min;
        Node next;

        public Node(int value, int min, Node next) {
            this.value = value;
            this.min = min;
            this.next = next;
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */



peilin
9个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Queue<SPFRange> minMaxSPFQ = new PriorityQueue<>();
        Map<Integer, Integer> coverMap = new TreeMap<>();

        int C = scanner.nextInt();
        int L = scanner.nextInt();

        while(C-- > 0) {
            int minSPF = scanner.nextInt();
            int maxSPF = scanner.nextInt();
            minMaxSPFQ.offer(new SPFRange(minSPF, maxSPF));
        }

        while(L-- > 0) {
            int spf = scanner.nextInt();
            int quantity = scanner.nextInt();

            coverMap.put(spf, coverMap.getOrDefault(spf, 0) + quantity);
        }

        int cnt = 0;
        while(!minMaxSPFQ.isEmpty() && !coverMap.isEmpty()) {
            SPFRange spfRange = minMaxSPFQ.poll();

            for(int spf: coverMap.keySet()) {
                if(spfRange.isInside(spf)) {
                    cnt++;
                    int quantity = coverMap.get(spf);
                    if(quantity - 1 > 0) {
                        coverMap.put(spf, quantity - 1);
                    } else {
                        coverMap.remove(spf);
                    }
                    break;
                }
            }
        }

        System.out.println(cnt);
    }

    public static class SPFRange implements Comparable<SPFRange>{
        private int minSPF, maxSPF;

        public SPFRange(int minSPF, int maxSPF) {
            this.minSPF = minSPF;
            this.maxSPF = maxSPF;
        }

        @Override
        public int compareTo(SPFRange that) {
            return this.maxSPF - that.maxSPF;
        }

        public boolean isInside(int SPF) {
            return SPF >= minSPF && SPF <= maxSPF;
        }
    }
}



peilin
9个月前
import java.util.*;

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

        int N = sc.nextInt();
        int M = sc.nextInt();
        int T = sc.nextInt();

        int[] row = new int[N];
        int[] col = new int[M];

        for(int i = 0; i < T; i++) {
            row[sc.nextInt() - 1]++;
            col[sc.nextInt() - 1]++;
        }

        if(T % N == 0 && T % M == 0) {
            long rowSwapNum = getNumOfSwap(T/N, N, row);
            long colSwapNum = getNumOfSwap(T/M, M, col);
            System.out.println("both " + (rowSwapNum + colSwapNum));
        } else if(T % N == 0) {
            long rowSwapNum = getNumOfSwap(T/N, N, row);
            System.out.println("row " + rowSwapNum);
        } else if(T % M == 0) {
            long colSwapNum = getNumOfSwap(T/M, M, col);
            System.out.println("column " + colSwapNum);
        } else {
            System.out.println("impossible");
        }
    }

    private static long getNumOfSwap(int avg, int len, int[] array) {
        long[] sum = new long[len];
        sum[0] = array[0] - avg;
        for(int i = 1; i < len; i++) {
            sum[i] = sum[i - 1] + (array[i] - avg);
        }
        Arrays.sort(sum);

        long mid = sum[len / 2];
        long numOfSwap = 0;
        for(int i = 0; i < len; i++) {
            numOfSwap += Math.abs(sum[i] - mid);
        }

        return numOfSwap;
    }
}



peilin
9个月前
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

        Map<Integer, Integer> langMap = new HashMap<>();

        // store in a hashMap, key is the language and 
        // value is the number of scientists who can understand this language
        int n = scanner.nextInt();
        for(int i = 0; i < n; i++) {
            int lang = scanner.nextInt();
            langMap.put(lang, langMap.getOrDefault(lang, 0) + 1);
        }

        int m = scanner.nextInt();
        int[] voiceLang = new int[m], subtitleLang = new int[m];
        for(int i = 0; i < m; i++) {
            soundLang[i] = scanner.nextInt();
        }
        for(int i = 0; i < m; i++) {
            subtitleLang[i] = scanner.nextInt();
        }

        int cinemaInd = -1, maxHappy = -1;
        for(int i = 0; i < m; i++) {
            // time 2 with the number of scientists who can understand the cinema sound
            // time 1 with the number of scientists who can understand the cinema sutitle
            int happy = 2 * langMap.getOrDefault(soundLang[i], 0) + langMap.getOrDefault(subtitleLang[i], 0);
            if(happy >  maxHappy) {
                cinemaInd = i;
                maxHappy = happy;
            }
        }

        System.out.println(cinemaInd + 1);
    }
}



peilin
9个月前
class Solution extends Relation {
    public int[] specialSort(int N) {
        List<Integer> sorted = new ArrayList<>();

        sorted.add(1);
        for(int i = 2; i <= N; i++) {
            int l = 0, r = sorted.size();
            while(l < r) {
                int mid = (l + r) / 2;
                if(compare(i, sorted.get(mid))) r = mid;
                else l = mid + 1;
            }

            sorted.add(l, i);
        }

        int[] result = new int[N];
        for(int i = 0; i < sorted.size(); i++) {
            result[i] = sorted.get(i);
        }
        return result;
     }
}