奖品分配-头条2019笔试题

有n个人参加编程比赛，比赛结束后每个人都得到一个分数；现在所有人排成一圈（第一个和第n个相邻）领取奖品，要求：

1、如果某个人的分数比左右的人高，那么奖品数量也要比左右的人多；

2、每个人至少得到一个奖品；

问最少应该准备多少个奖品。

输入格式

第一行是整数T，表示测试样例个数。

每个测试样例的第一行是一个整数n，表示参加比赛的人数。

第二行是n个正整数a[i]，表示从第1个人到第n个人的分数。

输出格式

对每个测试样例，输出应该准备的最少奖品，每个结果占一行。

数据范围

1≤T≤10,
0<n<\(10^5\),
0<a[i]<\(10^5\)

输入样例：

2
2
1 2
4
1 2 3 3

输出样例：

3
8

java 下标排序

//下标排序
int[] a = new int[n];
Integer[] idx = new Integer[n];
Arrays.sort(idx, (o1, o2)->a[o1]-a[o2]);

奖品分配问题

方法一、\(O(nlog_2^n)\)

我们希望当计算第i个小朋友糖果数量时，它左右分数比他低的小朋友糖果数量已经计算出来了，得分相同或大于没有要求。
因此，我们根据得分排序，得分少的先计算糖果数量。
如果左右未分配，则分配1
如果存在分配的，则分配该小朋友左右分配值中最大值+1

时间复杂度分析，计算次数为：

\[Tnlog_2^n = 10 \times 10^5log_2^{10^5} \approx 1.7\times10^7 \]

实测java超时， 可能排序常数项较大。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            
            Integer[] idx = new Integer[n];
            int[] nums = new int[n];
            for(int i=0; i < n; i++) {
                a[i] = sc.nextInt();
                idx[i] = i;
            }
            Arrays.sort(idx, (o1, o2)->a[o1]-a[o2]);
            for(int i=0; i < n; i++) {
                int k = idx[i];
                int left = (k-1+n)% n, right = (k+1)%n;
                int maxn = 0;
                if(a[left] < a[k]) maxn = Math.max(nums[left], maxn);
                if(a[right] < a[k]) maxn = Math.max(maxn, nums[right]);
                nums[k] = maxn + 1;
                //System.out.println("+++"+nums[k]);
            }
            long res = 0L;
            for(int i=0; i < n; i++)
                res = res + nums[i];
            System.out.println(res);
        }
    }
}

方法二、记忆化搜索\(O(n)\)

import java.util.*;
public class Main {
    static int[] f, a;
    static int n;
    static int dfs(int x) {
        if(f[x] != 0) return f[x];
        if(a[(x+n-1) % n] >= a[x] && a[(x+1) % n] >= a[x] ) 
            return f[x] = 1;
        int v = 0;
        if(a[(x+n-1)% n] < a[x]) 
            v = dfs((x+n-1)% n);
        if(a[(x+1)% n] < a[x]) 
            v = Math.max(v, dfs((x+1)%n));
        return f[x] = v + 1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0) {
            n = sc.nextInt();
            a = new int[n];
            f = new int[n];
            for(int i=0; i < n; i++)
                a[i] = sc.nextInt();
            for(int i=0; i < n; i++)
                dfs(i);
            long res = 0L;
            for(int i=0; i < n; i++)
                res = res + f[i];
            System.out.println(res);
        }
    }
}