前言

这一场难度也不是很简单了，题目越来越灵活了。所以可以提前做的同学抓紧提前做，后面不知道都出什么牛马题了。很明显越来越难了，150分已经不像前面那么好拿了。

1.分销粮食

粮食公司从农场收购了n吨粮食，现在要要平均分配给分销商进行销售(除不尽向下取整)。分销商数量若干，请计算分销商获得的粮食数量有几种可能。

解答要求

时间限制: C/C++ 2000ms,其他语言: 4000m内存限制:C/C++256MB,其他语言:512MB

输入

n:粮食总量，0<n<=4294967295

输出

m:分销商获得的粮食数有几种可能

样例1

 输入:5
 输出:3

思路与代码

模拟题。以下方法存在超时的风险，可能需要一些数学技巧进行优化。

n = int(input())
res = set()

i = 1

while True:
    res.add(n//i)
    if n // i == 1: break
    i += 1

print(len(res))

2.糖果迷富

小华和小为在一个两个m列的糖果迷宫里，迷宫的每一个位置上都有对应得糖果数目a[i][j],他们只能向右或者向下移动。

小华和小为都将从左上方a[0[[0]位置出发，向右下角a[1，m-1]走去，每到一个位置都将吃掉这个位置上的糖果。

假设小华先走，他走完后会吃模路过的糖果，然后小为才开始走，被小华吃掉的糖果，小为就能再吃了。

小华希望小为吃掉最少的糖果总数，然后小为也希望在小华走完后自己能吃掉更多的糖果总数。

请你帮忙计算小为最多可以吃掉多少糖果。

解答要求

时间限制:C/C++ 1000ms 其他语言2000ms，内存限制: C/C++ 256MB,其他语言:512MB

输入

第一行包含一个整数m(1<=m<=100000),标识迷宫的宽度。

接下来包含两行，每行包含m个整数，每一个整数a[i]j代表该位置的糖果数目。

输出

输出小为最多可以吃到多少糖果。

样例1

输入：3
     1 3 7
     3 5 1
输出：7
解释：1 3 7
     3 5 1
     小为吃掉小华选择吃掉粗体部分的糖果1、3、5、1，小为吃掉7

思路与代码

前缀模拟。

由于只有2行，所以无非就是枚举小华在哪里拐弯，这个点记为i，然后小为可以取得的总价值就是  第二行的前i个或者第一行的后n-i个。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[][] grid = new int[2][m];
        int[][] qzs = new int[2][m+1];

        for (int j = 0; j < m; j++) {
            grid[0][j] = sc.nextInt();
            qzs[0][j+1] = qzs[0][j] + grid[0][j];
        }

        for (int j = 0; j < m; j++) {
            grid[1][j] = sc.nextInt();
            qzs[1][j+1] = qzs[1][j] + grid[1][j];
        }


        long ans = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            int tmp = Math.max(qzs[1][i], qzs[0][m]-qzs[0][i+1]);
            ans = Math.min(ans, tmp);
        }

        System.out.println(ans);

    }

}

3.对战比赛

小明参加一个在线比赛。需要与n个对手对战。当小明的等级大于等于对手的等级，他就能赢。如果小明赢了，等级提升1级，否则会减少1级。对手的等级固定不变。小明的初始等级是x，小明想把他的等级提高到y（y>x）。

该比赛有一条规则：每局此赛小明只能选择和对战次数最少的对手进行对战，对战次

小明想用尽可能少的对站题升到等级y，计算小明为提升到等级y所需的最小可能的对战数。

注意，对手的等级不会改变，而小明的等级会改变。

解答要求

时间限制: C/C++ 2000ms,其他语言：4000ms 内存限制: C/C++ 256MB，其他语言：512MB

输入

第一行包含三个整数n、x和y(1<=n<=2* 10^5,1<=x<y<=10^12)表示对手个数，小明的初始等级和期望等级。

第二行包含n个整数a1,a2,a3,...,an(1<=ai<=10^12)表示对手的等级。

输出

打印小明为提升到等级y所需的最少对战数，如果不可能，则打印-1.

样例1

输入：7 2 10
     3 1 9 2 5 20 8
输出：20

思路与代码

贪心 + 模拟。

1. 每一次优先击败小等级的对手
2. 每一轮可以打败的人数记为cnt，那么每一轮增长的总次数为2*cnt - n。
3. 每一次可以击败的人的位置记为i，那么从i+1开始就开始打不过了，那么等级增长到i+1对应的等级的时候， 就应该更换策略了，通过这个差值可以算出需要轮询的次数了。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int n, cnt = 0;
        long x,y;

        long[] nums ;

        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        x = in.nextLong();
        y = in.nextLong();
        nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextLong();
        }

        Arrays.sort(nums);

        long[] diff = new long[n];

        for (int i = 0; i < n; i++) {
            diff[i] = Math.max(0, nums[i] - i);
            if (diff[i] <= x) cnt++;
        }

        if (x+cnt >= y) {
            System.out.println(y-x);
            return;
        }
        if (n-cnt >= cnt) {
            System.out.println(-1);
            return;
        }
        long ans = 0;
        while (x < y) {
            int l = 0, r = n-1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (diff[mid] <= x) l = mid;
                else r = mid - 1;
            }
            if (r == n-1) {
                System.out.println(ans + y - x);
                return;
            }
            r++;
            int cur = 2*r - n;
            long next = Math.min(diff[r], y);
            long d = next - x;
            if (next == y && d <= r) {
                System.out.println(ans + d);
                return;
            }
            if (cur < 0) {
                System.out.println( -1);
                return;
            }
            long time = d / cur;
            ans += time * n;
            x += cur * time;

        }
        System.out.println(ans);
    }

}