【深基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 \leq n \leq 10^6\)，\(0 \leq a_i,q \leq 10^9\)，\(1 \leq m \leq 10^5\)
本题输入输出量较大，请使用较快的 IO 方式。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
void calc(int q,vector<int> &a,int n)
{
int L=0,R=n+1;
while(L+1<R)
{
int M=(L+R)>>1;
if(a[M]<q) L=M;
else R=M;
}
if(a[R]==q) cout<<R<<' ';
else cout<<"-1 ";
}
void solve()
{
int n,m;
cin>>n>>m;
vector<int> a(n+1);
for(int i=1;i<=n;++i) cin>>a[i];
while(m--)
{
int q;
cin>>q;
calc(q,a,n);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
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 \leq N \leq 2000\)。
对于 \(100\%\) 的数据，\(1 \leq N \leq 2 \times 10^5\)，\(0 \leq a_i <2^{30}\)，\(1 \leq C < 2^{30}\)。
2017/4/29 新添数据两组
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
void solve()
{
int n,c;
cin>>n>>c;
for(int i=0;i<n;++i) cin>>a[i];
sort(a,a+n);
long long res=0;
for(int i=0;i<n;++i)
res+=(upper_bound(a,a+n,a[i]+c)-lower_bound(a,a+n,a[i]+c));
cout<<res<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
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\le10^6\)，\(1\le M\le2\times10^9\)，树的高度 \(<10^9\)，所有树的高度总和 \(>M\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N];
int n,m;
long long calc(int x)
{
long long res=0;
for(int i=1;i<=n;++i) if(a[i]>x) res+=a[i]-x;
return res;
}
void solve()
{
//int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>a[i];
int L=-1,R=1e9;
while(L+1<R)
{
int M=L+(R-L)/2;
//cout<<calc(M)<<'\n';
if(calc(M)>=m) L=M;
else R=M;
}
cout<<L<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}
[NOIP2001 提高组] 一元三次方程求解（牛顿迭代）
题目描述
有形如：\(a x^3 + b x^2 + c x + 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<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double f(double x)
{
return a*x*x*x+b*x*x+c*x+d;
}
double df(double x)
{
return 3*a*x*x+2*b*x+c;
}
void calc(double l,double r)
{
double x0=(l+r)/2;
double x;
while(fabs(f(x0))>1e-6)
{
x=x0-f(x0)/df(x0);
x0=x;
}
cout<<fixed<<setprecision(2)<<x0<<' ';
}
void solve()
{
cin>>a>>b>>c>>d;
double p=(-b-sqrt(b*b-3*a*c))/(3*a);
double q=(-b+sqrt(b*b-3*a*c))/(3*a);
calc(-100,p);
calc(p,q);
calc(q,100);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}