【深基13.例1】查找

题目描述

输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots ,a_n$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。

输入格式

第一行 $2$ 个整数 $n$ 和 $m$，表示数字个数和询问次数。

第二行 $n$ 个整数，表示这些待查询的数字。

第三行 $m$ 个整数，表示询问这些数字的编号，从 $1$ 开始编号。

输出格式

输出一行，$m$ 个整数，以空格隔开，表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证，$1\le n\le 10^6$，$0\le a_i,q\le 10^9$，$1\le m\le 10^5$

本题输入输出量较大，请使用较快的 IO 方式。

#include<iostream>
#define MAXN 1000010
using namespace std;
int a[MAXN],m,n,q;
int find(int x){
    int l = 1,r = n+1;
    while(l<r){
        int mid = (l+r)>>1;
        if(a[mid]>=x)r  = mid;
        else l = mid +1;
    }
    if(a[l]==x)return l;
    else return -1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i =1;i<=m;i++){
        cin>>q;
        cout<<find(q)<<" ";
    }
    return 0;
}

A-B 数对

题目背景

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A-B=C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个正整数 $N,C$。

第二行，$N$ 个正整数，作为要求处理的那串数。

输出格式

一行，表示该串正整数中包含的满足 $A-B=C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据，$1\le N\le 2000$。

对于 $100\%$ 的数据，$1\le N\le 2\times 10^5$，$0\le a_i<2^{30}$，$1\le C<2^{30}$。

2017/4/29 新添数据两组

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 200010
LL  a[maxn];
int n,c;
int main(){
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    sort(a,a+n);
    LL tot = 0;
    for(int i=0;i<n;i++)
        tot += upper_bound(a, a+n, a[i]+c) - lower_bound(a, a+n, a[i]+c);
    printf("%lld",tot);
    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200010
typedef long long LL;
LL a[maxn];
int n,c;
int main(){
    scanf("%d%d",&n,&c);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    sort(a,a+n);
    LL tot = 0;
    for(int i=0,L=0,R=0;i<n;i++){
        while(L<n&&a[L]<a[i]+c)L++;
        while(R<n&&a[R]<=a[i]+c)R++;
        tot += R-L;
    }
    printf("%lld",tot);
    
    return 0;
}

[COCI2011-2012#5] EKO / 砍树

题目描述

伐木工人 Mirko 需要砍 $M$ 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。

Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 $H$（米），伐木机升起一个巨大的锯片到高度 $H$，并锯掉所有树比 $H$ 高的部分（当然，树木不高于 $H$ 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 $20,15,10$ 和 $17$，Mirko 把锯片升到 $15$ 米的高度，切割后树木剩下的高度将是 $15,15,10$ 和 $15$，而 Mirko 将从第 $1$ 棵树得到 $5$ 米，从第 $4$ 棵树得到 $2$ 米，共得到 $7$ 米木材。

Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 $H$，使得他能得到的木材至少为 $M$ 米。换句话说，如果再升高 $1$ 米，他将得不到 $M$ 米木材。

输入格式

第 $1$ 行 $2$ 个整数 $N$ 和 $M$，$N$ 表示树木的数量，$M$ 表示需要的木材总长度。

第 $2$ 行 $N$ 个整数表示每棵树的高度。

输出格式

$1$ 个整数，表示锯片的最高高度。

样例 #1

样例输入 #1

4 7
20 15 10 17

样例输出 #1

15

样例 #2

样例输入 #2

5 20
4 42 40 26 46

样例输出 #2

36

提示

对于 $100\%$ 的测试数据，$1\le N\le 10^6$，$1\le M\le 2\times 10^9$，树的高度 $<10^9$，所有树的高度总和 $>M$。

#include<cstdio>
using namespace std;
#define maxn 1000010
typedef long long LL;
LL a[maxn], n,m;
bool P(int h){
    LL tot = 0;
    for(int i=1;i<=n;i++)
        if(a[i]>h)
            tot += a[i] - h;
    return tot>=m;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    int L=0,R=1e9,ans,mid;
    while(L<=R)
        if(P(mid=L+R>>1))
            ans = mid,L=mid+1;
        else
            R = mid -1;
    printf("%d",ans);
    return 0;
}

进击的奶牛

题目描述

Farmer John 建造了一个有 $N$（$2\le N\le 10^5$) 个隔间的牛棚，这些隔间分布在一条直线上，坐标是 $x_1,x_2,\cdots ,x_N$（$0\le x_i\le 10^9$）。

他的 $C$（$2\le C\le N$）头牛不满于隔间的位置分布，它们为牛棚里其他的牛的存在而愤怒。为了防止牛之间的互相打斗，Farmer John 想把这些牛安置在指定的隔间，所有牛中相邻两头的最近距离越大越好。那么，这个最大的最近距离是多少呢？

输入格式

第 $1$ 行：两个用空格隔开的数字 $N$ 和 $C$。

第 $2\sim N+1$ 行：每行一个整数，表示每个隔间的坐标。

输出格式

输出只有一行，即相邻两头牛最大的最近距离。

样例 #1

样例输入 #1

5 3
1
2
8
4
9

样例输出 #1

3

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1000010
#define INF 1e9
int a[maxn],n,c;
bool P(int d){
    int k=0,last=-INF;
    for(int i=1;i<=n;i++)
        if(a[i]-last>=d)
            last = a[i],k++;
    return k>=c;
}
int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int L=0,R=INF,ans,mid;
    while(L<=R)
        if(P(mid=L+R>>1))ans = mid,L=mid+1;
        else R=mid-1;
    printf("%d",ans);
}

[NOIP2001 提高组] 一元三次方程求解

题目描述

有形如：$a{x}^3+b{x}^2+cx+d=0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。

提示：记方程 $f(x)=0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1<x_2$，$f(x_1)\times f(x_2)<0$，则在 $(x_1,x_2)$ 之间一定有一个根。

输入格式

一行，$4$ 个实数 $a,b,c,d$。

输出格式

一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

样例 #1

样例输入 #1

1 -5 -4 20

样例输出 #1

-2.00 2.00 5.00

提示

【题目来源】

NOIP 2001 提高组第一题

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define eps 1e-4
double A,B,C,D;
double f(double x){
    return A*x*x*x +B*x*x+C*x+D;
}
int main(){
    cin>>A>>B>>C>>D;
    for(int i=-100;i<=100;i++){
        double L = i,R=i+1,mid;
        if(fabs(f(L))<eps)printf("%.2lf ",L);
        else if(fabs(f(R))<eps)continue;
        else if(f(L)*f(R)<0){
            while(R-L>eps){
                mid = (L+R)/2;
                if(f(mid)*f(R)>0)R = mid;
                else L = mid;
            }
            printf("%.2lf ",L);
        }
    }
}