AcWing打开-2041-干草堆

2041. 干草堆

题目描述

贝茜对她最近在农场周围造成的一切恶作剧感到抱歉,她同意帮助农夫约翰把一批新到的干草捆堆起来。
开始时,共有 N 个空干草堆,编号 1∼N。
约翰给贝茜下达了 K 个指令,每条指令的格式为 A B,这意味着贝茜要在 A..B 范围内的每个干草堆的顶部添加一个新的干草捆。
例如,如果贝茜收到指令 10 13,则她应在干草堆 10,11,12,13 中各添加一个干草捆。
在贝茜完成了所有指令后,约翰想知道 N 个干草堆的中值高度——也就是说,如果干草堆按照高度从小到大排列,位于中间的干草堆的高度。
方便起见,N 一定是奇数,所以中间堆是唯一的。
请帮助贝茜确定约翰问题的答案。

输入格式

第一行包含 N 和 K。
接下来 K 行,每行包含两个整数 A,B,用来描述一个指令。

输出格式

输出完成所有指令后,N 个干草堆的中值高度。

数据范围

1≤N≤106,
1≤K≤25000,
1≤A≤B≤N

tags: 差分、排序

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        while(k-- > 0) {
            int A = sc.nextInt(), B = sc.nextInt();
            a[A-1]++;
            if(B < n) {
                a[B]--;
            }
        }
        for(int i = 1;i < n;i++) {
            a[i] = a[i-1] + a[i];
        }
        Arrays.sort(a);
        System.out.println(a[n/2]);
    }
}

这里再记录一下差分是什么,什么时候用差分。

首先回答什么是差分:如果数组\(A\)是数组\(B\)的前缀和,那么数组\(B\)就是数组\(A\)的差分。

举个栗子:

AcWing打开-2041-干草堆

什么时候用差分:我们构造一个数组的差分数组,是为了频繁对数组中某一区间进行同一操作,例如将序列中\([l,r]\)之间的每个数都加上\(c\)这一操作,可能执行\(n\)次且每次的\(c\)不同,如果对原数组进行操作,每次操作都会花费\(O(n)\)的时间复杂度,如果使用该数组的差分数组进行操作,那么每次操作的复杂度就为\(O(1)\)。然后求差分数组的前缀和即为所求的结果。

如考虑给数组\(s\)的区间\([l, r]\)中每个数加上\(c\),等价于对差分数组\(q\)操作:\(q[l]+=c,q[r+1]-=c\),因为\(q[i]=s[i]-s[i-1]\)。

以下给出C++的模板用于构造差分。

#include<bits/stdc++.h> 
using namespace std; 
int n,m,q,last,sum[10086],b[10086],s[10086]; 
int main() 
{ 
	cin>>n;//n个数  
	for(int i=1,x;i<=n;i++) 
	{ 
		cin>>x;//这里实际上不需要a数组,视题而异  
		b[i]=x-last;//得到差分数组  
		last=x;//别忘了变化last变量  
	} 
	cin>>m;//m次操作 
	for(int i=1,l,r,del;i<=m;i++) 
	{ 
		 cin>>l>>r>>del;//在[l,r] 加上del 
		 b[l]+=del,b[r+1]-=del;  
	} 
	for(int i=1;i<=n;i++) 
	{ 
		s[i]=s[i-1]+b[i];//这里是处理我们的s数组  
		sum[i]=sum[i-1]+s[i];//处理我们的sum数组.  
	} 
	cin>>q;//q个询问  
	for(int i=1,l,r;i<=q;i++) 
	{ 
		cin>>l>>r; //询问[l,r]的区间和. 
		cout<<sum[r]-sum[l-1]<<endl; //输出即可.  
	} 
}

故而本题C++代码如下:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int s[N], q[N];
// 构造以及计算差分数组
//给s区间[l, r]中的每个数加上c等价于对数组q操作:q[l] += c, q[r + 1] -= c
void insert(int l, int r, int c)
{
    q[l] += c;
    q[r + 1] -= c;
}
int main()
{
    int n, k;
    cin >> n >> k;
    // 如果s[i]有初始值使用下面代码,赋初始值同时构造差分数组q
    // for(int i = 1; i <= n; i ++)
    // {
    //     s[i] = 0;
    //     insert(i, i, s[i]);
    // }
    while(k --)
    {
        int a, b;
        cin >> a >> b;
        insert(a, b, 1);  //每次在a到b之间草堆添加一堆
    }
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + q[i];  //求出差分数组q的前缀和
    sort(s, s + n);  //排序
    printf("%d\n", s[n / 2]);  //求中位数
    return 0;
}

同时看到一个大佬的Java输入模板,在这里记录一下。

import java.io.*;
import java.util.*;
static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader() {
        reader = new BufferedReader(new InputStreamReader(System.in), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
}
static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
static int lcm(int a, int b) { return (a * b) / gcd(a, b); }
上一篇:AcWing基础算法(三)


下一篇:AcWing 615. 油耗