题解 P3184 【[USACO16DEC]Counting Haybales数草垛】

Dr_殇 · 2017-10-15 15:45:40 · 题解

我很可怜p党，他们的函数库没有我们cpp多，sort都没有。这道题，cpp党很好做，因为algorithm库里有两个叫upper_bound和lower_bound的函数，他们的作用就是二分找比某个数小并与它最接近的那个数的下标和二分找比某个数大并与它最接近的那个数的下标。知道这两个函数后，特别简单。

代码如下：

#include <ctime>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>//头文件准备，algorithm必须加，要不然编译不过
using namespace std;
int n,m,a[100005];
int main(){
    scanf ("%d %d",&n,&m);//读入
    for (int i=1;i<=n;i++){
        scanf ("%d",&a[i]);
    }
    sort (a+1,a+1+n);//注意：二分查找要排序，要不然就是在乱找
    for (int i=1;i<=m;i++){
        int x,y;
        scanf ("%d %d",&x,&y);//读入两个数
        printf("%d\n",upper_bound(a+1,a+n+1,y)-lower_bound(a+1,a+n+1,x));//注意：y是后面一个数，所以是先查后面一个数，再相减
    }
    while (1);//反抄袭
    return 0;
}