NC200443. 亚丝娜sama
描述
众所周知桐人能砍子弹，但是有人想用数量伤到桐人，所以他带着一群人来攻击桐人。
桐人想知道他在第 k 秒时需要砍多少颗子弹，但是他砍子弹已经很辛苦了，所以他来找聪明的你来帮他算一算。
他有tt次询问，每次询问一个 k 。
子弹从发射到击中桐人要 m 秒，有 n 个人射击，每1秒射出一发子弹（弹夹足够大不需要换子弹，一旦开始就不会停），
现给出你这 n 个人开始射击的时间，请你帮帮桐人吧。
输入描述
第一行3个整数n,m,t用空格分开（0<= n <= 100 000,1<= m<= 100 000,1<= t<= 100 000）。
第二行是 n 个正整数 ai 表示第 i 个人开始射击的时间（0<= ai <= 100 000）。
接下来tt行，每行一个数字 k（0<= k<= 300 000）。
输出描述
请输出 t 行，每行一个答案（第 k 秒需要砍的子弹数目）
示例1
输入:
5 1 2 0 1 2 2 3 2 3
输出:
2 4
C(clang 3.9) 解法, 执行用时: 107ms, 内存消耗: 17824K, 提交时间: 2019-12-17 21:04:44
#include <stdio.h>
int a[4000005]={0};
int main()
{
int n,m,k,t,i,j;
scanf("%d%d%d",&n,&m,&t);
for(i=0;i<n;i++)
{
scanf("%d",&j);
a[j]=a[j]+1;
}
for(i=1;i<=4000000;i++)
a[i]=a[i]+a[i-1];
while(t--)
{
scanf("%d",&k);
if(k<m)
printf("0\n");
else
printf("%d\n",a[k-m]);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 46ms, 内存消耗: 2656K, 提交时间: 2020-03-09 16:07:26
#include<bits/stdc++.h>
using namespace std;
int s[300005],S[300005];
int main()
{
int i,n,m,q;
scanf("%d%d%d",&n,&m,&q);
while(n--)scanf("%d",&i),s[m+i]++;
for(i=1;i<=300000;i++)S[i]=S[i-1]+s[i];
while(q--)scanf("%d",&i),printf("%d\n",S[i]);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 270ms, 内存消耗: 1368K, 提交时间: 2020-05-22 21:08:48
#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[100010];
int main(){
scanf("%d %d %d",&n,&m,&t);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
a[i]+=m;
}
sort(a,a+n);
for(int i=0;i<t;i++){
int k;
cin>>k;
cout<<(upper_bound(a,a+n,k)-a)<<endl;
}
}