hihoCoder Offer收割赛61简要分析

0
0

offer61 题解

最小排列

设 $c$ 是不在 $b$ 中的数组成的序列,将 $c$ 排序,然后将 $b$ 和 $c$ 归并即可。时间复杂度:$O(n)$

最大前缀和

枚举每个前缀,考虑维护两个set,一个是在前缀里的数的集合,一个是不在前缀里的数的集合。每次交换肯定是用前缀里最小的数去换不在前缀里的最大的数,模拟一下即可,时间复杂度:$O(nk\log{n})$

质数

考虑传统的筛法,枚举$10^6$以内的质因子,去筛这些数,例如枚举到了质数$x$,只要枚举区间$[l,r]$内$x$的倍数即可,时间复杂度是$O((r-l)\log{l})$的

随机排列2

考虑在第$i$步时$x$改变的概率,那么$p[i]$一定是$p[1..i]$中的最大值,这个概率是$\frac{1}{i}$。

所以答案是$n!*\sum_{i=1}^{n}\frac{1}{i}$

时间复杂度:$O(n)$

3 answer(s)

0

看不懂过D的人写的是什么QAQ

0

有个疑问,B题按照你的思路写的,但是有个小细节搞不明白,就是下面注释的那行代码,为什么不加max[i+1][j]>min[i][j]判断就会WA,我感觉不需要加也能AC。 是不是OJ有啥Corner case?多谢

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(), k=sc.nextInt();
        long[]a=new long[n];
        for(int i=0;i<n;i++)a[i]=sc.nextLong();

        long[][]min=new long[n][k], max=new long[n][k];
        for(int i=0;i<n;i++) Arrays.fill(min[i], Long.MAX_VALUE);
        for(int i=0;i<n;i++) Arrays.fill(max[i], Long.MIN_VALUE);
        PriorityQueue<Long>pq=new PriorityQueue<Long>();
        for(int i=0;i<n;i++) {
            pq.add(a[i]);
            List<Long>tmp=new ArrayList<Long>();
            for(int j=0;j<Math.min(i+1, k);j++) {
                long t = pq.remove();
                tmp.add(t);
                min[i][j]=((j==0?0:min[i][j-1])+t);
            }
            for(long t:tmp) pq.add(t);
        }
        PriorityQueue<Long>pq2=new PriorityQueue<Long>();
        for(int i=n-1;i>=0;i--) {
            pq2.add(-a[i]);
            List<Long>tmp=new ArrayList<Long>();
            for(int j=0;j<Math.min(n-i, k);j++) {
                long t = pq2.remove();
                tmp.add(t);
                max[i][j]=((j==0?0:max[i][j-1])-t);
            }
            for(long t:tmp) pq2.add(t);
        }

        long res = Long.MIN_VALUE, sum = 0;
        for(int i=0;i<n;i++) {
            sum += a[i];
            res = Math.max(res, sum);
            for(int j=0;j<Math.min(i+1, k);j++) {
                if(i+1<n && max[i+1][j]>min[i][j]) // **为什么这里需要额外判断一下max[i+1][j]>min[i][j]才能AC**
                    res = Math.max(res, sum-min[i][j]+max[i+1][j]);
            }
        }
        System.out.println(Math.max(res, 0));
    }
1

默默宣传一下自己的博客:https://www.cnblogs.com/fzl194/p/9097471.html

write answer 切换为英文 切换为中文


转发分享