首页 > 其他分享 >题单:二分

题单:二分

时间:2023-09-22 16:24:50浏览次数:35  
标签:二分 10 Mirko int double 样例 leq 题单

【深基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;
}

标签:二分,10,Mirko,int,double,样例,leq,题单
From: https://www.cnblogs.com/ruoye123456/p/17722663.html

相关文章

  • 随想录Day1|704. 二分查找、27. 移除元素
    随想录Day1|704.二分查找、27.移除元素 704.二分查找LeetCode题目文章讲解视频讲解给定n个元素升序的整形数组nums和一个目标值target,写一个函数搜索nums中的target,如果存在目标值则返回下标,否则返回-1。其中nums中的元素不重复,n在[1,10000]之间,nums的每个元素都在[-......
  • 算法学习 |Day 1 数组基础 704. 二分查找,27. 移除元素
    704.二分查找思路:二分查找的前置条件是数组有序且无重复元素,每次通过改变边界值来缩小查找范围。自己写的:可以看到对边界的判断存在问题,基本思路是左闭右闭,但是while循环的判断是按照左闭右开来写的。对于数组中仅包含一个元素且该元素是目标函数的情况会出错。重新调试后......
  • 代码源:合并数列(二分)
    有n个线性序列,第i个序列可以表示成ki×x+bi的形式(x=0,1,2,...)。请问将这些序列中的数按从小到大的顺序合并起来,前m个数分别是多少(重复出现的数合并后也会出现多次)?输入格式第一行一个整数n。接下来n行每行两个整数ki,bi。最后一行一个整数m。输出格式输......
  • LeetCode 周赛上分之旅 #46 经典二分答案与质因数分解
    ⭐️本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和BaguTreePro知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场LeetCode周赛的解题报告,一......
  • 二分图相关结论
    最小点覆盖:定义:选择最少的点,使得每条边都有一端被选。结论:二分图的最小点覆盖等于二分图最大匹配构造方案:从所有左侧未匹配的点出发,先走一条未匹配边,然后走一条匹配边,把所有走过的点标记,选择左边所有未标记的点和右边所有标记的点。最大独立集定义:选择最多的点,使得他们之间两......
  • 基础二分算法:整数二分、浮点二分
    1、整数二分以acwing789为例,题目要求如下:第一行输入整数n和q,表示数组长度和询问个数。第二行输入数组,包含n个整数。接下来q行,每一行一个整数k,表示一个问询元素。要求输出q行,每行包含两个整数,表示所求元素的起始位置和终止位置。如果数组中不存在该元素,则返回-1-1。#inc......
  • # 二分法
    l.sort()defindex(l,target_num):iflen(l)==0:print('没找到')returnmiddle_index=len(l)//2ifl[middle_index]<target_num:l_right=l[middle_index+1:]re......
  • 【学习笔记】(26) cdq 分治 与 整体二分
    cdq分治基本思想我们要解决一系列问题,这些问题一般包含修改和查询操作,可以把这些问题排成一个序列,用一个区间[L,R]表示。分。递归处理左边区间\([L,M]\)和右边区间\([M+1,R]\)的问题。治。合并两个子问题,同时考虑到\([L,M]\)内的修改对\([M+1,R]\)内的查询产生的影......
  • HDU 1054 Strategic Game 树形DP/二分图匹配
    第一次写博文,想了半天就拿一道dp/graph的题作为处作吧此题有两种常见解法(题意比较简单,就不赘述)1.二分图最大匹配       此题等价于问一棵树中最小点覆盖数。树形结构可以把它看做是一个二分图,一个点集为奇数层,另一个点集为偶数层,显然满足二分图定义,可以套用求二分图最小点......
  • 2023.9.14 整数二分排序
    1#二分23##整数二分45~~~c++6//区间[l,r]被划分成[l,mid]和[mid+1,r]时使用7inttest01(intl,intr)8{9while(l<r)10{11intmid=(l+r)/2;12boolcheck(intmid);//check判断mid是否满足x性质13if(check(......