头条笔试-文件传输

目录

1. 输入描述
2. 输出描述
3. 示例
   1. 示例1
   2. 示例2

解答

题目描述

服务器正在做数据备份，需要传输一批文件。在任意时间只能有一个文件被传输，一个文件传输需要一秒。
现在有n批文件，我们知道这批文件加入传输队列的是时间t（单位秒），以及这批文件的个数c。
传输队列的文件会以一秒一个文件的速度进行传输。
现在负责传输文件的同学想知道，所有文件被传输完成的时刻，以及传输队列中文件堆积的最大数量。

输入描述

第一行一个整数n，代表有n批文件。
接下来n行每行两个整数t，c，代表这批文件加入队列的时间和这批文件的个数。

对于 50% 的数据：
1<=n<=10^3
1<=t, c<=10^6

对于 100% 的数据：
1<=n<=10^5
1<=t, c<=10^9

输出描述

输出一行两个整数，所有文件被传输完的时刻和传输队列中文件堆积的最大数量。

示例

示例1

输入

3
1 1
2 1
3 1

输出

4 1

示例2

输入

3
1 3
2 3
3 3

输出

10 7

解答

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

public class Main {

    static class MyComparator implements Comparator<int[]> {
        @Override
        public int compare(int[] a, int[] b) {
            return a[0] - b[0];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [][]d = new int[n][2];
        long []p = new long[n];
        for (int i = 0; i < n; i++) {
            d[i][0] = sc.nextInt();
            d[i][1] = sc.nextInt();
        }
        Comparator<int[]> cmp = new MyComparator();
        Arrays.sort(d, cmp);
        for (int i = 1; i < n; i++) {
            p[i] = Math.max(0, d[i-1][1] - d[i][0] + d[i-1][0] + p[i-1]);
        }
        long max_v = 0;
        for (int i = 0; i < n; i++) {
            max_v = Math.max(p[i] + d[i][1], max_v);
        }
        long ft = p[n-1] + d[n-1][1] + d[n-1][0];

        System.out.println(ft + " " + max_v);
    }
}