AtCoder Beginner Contest 322 Problem C - Festival 题解

Meaning - 题意简述

给定 \(N\) 和 \(M\)，还有 \(M\) 个正整数 \(a_1 \sim a_n\)，对于每个 \(i \le n\)，求出 \(a\) 中第一个大于等于 \(i\) 的整数和 \(i\) 的差。

Solution - 题解思路

题目保证 \(a\) 数组单增，所以就可以用二分函数 lower_bound 来寻找答案。

lower_bound 的用法为：

lower_bound(a + 1,a + m + 1,x) - a，表示 \(a\) 数组中第一个大于等于 \(x\) 的数的地址，要减去 \(a\) 的地址（也就是 \(a_0\) 的地址）才能得到位置。

Accept Code - 代码

Accept Record

#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 2e5 + 10;

int n,m,a[MAXN];

int main(){
  cin >> n >> m;
  for (int i = 1; i <= m; i++){
    cin >> a[i];
  }
  sort(a + 1,a + m + 1);
  for (int i = 1; i <= n; i++){
    cout << a[lower_bound(a + 1,a + m + 1,i) - a] - i << '\n';
  }
  return 0;
}