洛谷刷题9

二分 - OI Wiki (oi-wiki.org)

二分法

定义

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

最大值最小化

注意，这里的有序是广义的有序，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做 1，不满足看做 0，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。

要求满足某种条件的最大值的最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的「最大值」，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快地找到答案。因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：

  1. 答案在一个固定区间内；
  2. 可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
  3. 可行解对于区间满足一定的单调性。换言之，如果 x 是符合条件的，那么有x+1 或者 x-1符合。

当然，最小值最大化是同理的。

STL 的二分查找

C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中。

二者均采用二分实现，所以调用前必须保证元素有序。

【深基13.例1】查找

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

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 方式。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int M = 10000000;
int a[M];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	while (m--)
	{
		int x;
		cin >> x;
		int l = 0;
		int r = n+1;

		while (l+1<r)
		{
			int mid = (l + r) / 2;
			if (a[mid]<x)
			{
				l = mid;
			}
			else
			{
				r = mid;
			}
		}
		if (a[r]==x )
		{
			cout<< r<<" ";
		}
		else
		{
			cout << "-1"<<" ";
		}
	}
	return 0;
}

题解的lower_bound写法
    int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意-a
		if(x!=a[ans]) printf("-1 ");//没有，输出-1
		else printf("%d ",ans);//有，输出ans

A-B 数对

题目背景

出题是一件痛苦的事情！

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

题目描述

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

输入格式

输入共两行。

第一行，两个正整数 \(N,C\)。

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

输出格式

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

样例 #1

样例输入 #1

1
2
4 1
1 1 2 3

样例输出 #1

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 新添数据两组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int a[N];
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
int main()
{
int n;
cin>>n;
int  c;
cin>>c;
rep(i,1,n)
{
    cin>>a[i];
}
sort(a+1,a+1+n);
int l=0;
int r=0;
ll ans=0;
rep(i,1,n)
{
    while(a[i]>a[l]-c&&l<=n )
    {
        l++;
    }
    //找到第一个大于或等于
    while(a[i]>=a[r]-c&&r<=n)
   {
    r++;
   }
    //找到第一个大于
   if(a[l]-a[i]==c)
   {
       ans += r - l;
   }

}
cout<<ans;
}

题解也有映射做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  #include <iostream>
    #include <map>
    using namespace std;
    typedef long long LL;
    LL a[200001];
    map<LL,LL> m;//建立一个数字到出现次数的映射 map<num,times>
    //A-B=C --> A-C=B
    int main() {
        int n;
        LL c;
        LL ans=0;
        cin >> n >> c;
        for(int i=1;i<=n;i++) {
            cin >> a[i];
            m[a[i]]++;
            a[i]-=c;    
        } 
        for(int i=1;i<=n;i++) ans+=m[a[i]];
        cout << ans << endl;
        return 0;
}
//好办法！

也有stl做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
long a[200001];
long N,C,ans;
int main()
{
    cin>>N>>C;
    for(int i=1;i<=N;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+N+1);
    for(int i=1;i<=N;i++)
    {
        ans+=((upper_bound(a+1,a+N+1,a[i]+C)-a)-(lower_bound(a+1,a+N+1,a[i]+C)-a));
    }
    cout<<ans;
    return 0;
}

[COCI 2011/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

1
2
4 7
20 15 10 17

样例输出 #1

1
15

样例 #2

样例输入 #2

1
2
5 20
4 42 40 26 46

样例输出 #2

1
36

提示

对于 \(100\%\) 的测试数据，\(1\le N\le10^6\)，\(1\le M\le2\times10^9\)，树的高度 \(\le 4\times 10^5\)，所有树的高度总和 \(>M\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a[100000000];
int n, m;
bool check(int x)
{
	long long sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += max(0, a[i] - x);

	}
	if (sum>=m)
	{
		return true;
	}
	else
	{
		return false;
	}

}
int main()
{

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);

	int h = a[n - 1];
	int l = -1;
	int r = h+1;
	while (l+1<r)
	{
		int mid = (l + r) / 2;
		if (check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	if (check(r))
	{
		cout << r;
	}
	else { 
		cout << l;
    }
}
//暴力究极解法

[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
1 -5 -4 20

样例输出 #1

1
-2.00 2.00 5.00

提示

【题目来源】

NOIP 2001 提高组第一题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
using namespace std;
double a, b, c, d;

double f(double x)
{

	return a * x * x * x + b * x * x + c * x + d;
}
void find(double l, double r)
{
	if (r-l<0.001)
	{
		printf("%.2f ", r);
		return ;
	}
	double mid = (l + r) / 2;
	if (f(mid)==0)
	{
		printf("%.2f ", mid);
		return;
	}
	if (f(mid)*f(l)<0)
	{
		find(l, mid);
	}
	else
	{
		find(mid, r);
	}
}
int main()
{
	int mark = 0;
	cin >> a >> b >> c >> d;
	for (double i = -100; i <100,mark!=3; i++)
	{
		if (f(i)==0)
		{
			printf("%.2f ", i);
			mark++;
			continue;
		}
		if (f(i)*f(i+1)<0)
		{
			find(i, i + 1);
			mark++;
		}
        //有根找根
	}
    return 0;
}

烦恼的高考志愿

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

题目描述

现有 \(m\) 所学校，每所学校预计分数线是 \(a_i\)。有 \(n\) 位学生，估分分别为 \(b_i\)。

根据 \(n\) 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 \(m,n\)。\(m\) 表示学校数，\(n\) 表示学生数。

第二行共有 \(m\) 个数，表示 \(m\) 个学校的预计录取分数。第三行有 \(n\) 个数，表示 \(n\) 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

样例 #1

样例输入 #1

1
2
3
4 3
513 598 567 689
500 600 550

样例输出 #1

1
32

提示

数据范围：

对于 \(30\%\) 的数据，\(1\leq n,m\leq1000\)，估分和录取线 \(\leq10000\)；

对于 \(100\%\) 的数据，\(1\leq n,m\leq100000\)，估分和录取线 \(\leq 1000000\) 且均为非负整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
using ll = long long;
ll m, n;
ll a[1001000], b[1001000];
ll ans;
ll sum;
ll s;
ll find(int x) {
	int l = 0, r = m + 1;
	while (l +1< r) {
		int mid = (l + r) / 2;
		if (a[mid] < x)l = mid;
		else r = mid ;
	}
	if(x <= a[1])//这里需要特判断一下，不然只能得70分
	{
		ans = a[1] - x;
	}
	else {
		 if (abs(a[l] - x) < abs(a[l+1] - x)) {
			ans = abs(a[l] - x);
		}
		else {
			ans = abs(a[l+1] - x);
			
		}
	}
	return ans;
}
int main() {
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
	}
	for (int j = 1; j <= n; j++) {
		cin >> b[j];
		s += b[j];
	}
	sort(b + 1, b + 1 + n);

	sort(a + 1, a + 1 + m);
	for (int k = 1; k <= n; k++) {
	
		sum +=find(b[k]);
	}
	cout << sum;
	return 0;
}

[NOIP2015 提高组] 跳石头

题目背景

NOIP2015 Day2T1

题目描述

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 \(M\) 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L \geq 1\) 且 \(N \geq M \geq 0\)。

接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i\,( 0 < D_i < L)\)， 表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

样例输出 #1

1
4

提示

输入输出样例 1 说明

将与起点距离为 \(2\) 和 \(14\) 的两个岩石移走后，最短的跳跃距离为 \(4\)（从与起点距离 \(17\) 的岩石跳到距离 \(21\) 的岩石，或者从距离 \(21\) 的岩石跳到终点）。

数据规模与约定

对于 \(20\%\)的数据，\(0 \le M \le N \le 10\)。
对于 \(50\%\) 的数据，\(0 \le M \le N \le 100\)。
对于 \(100\%\) 的数据，\(0 \le M \le N \le 50000,1 \le L \le 10^9\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
int length, n, m, a[500005], l, r, now, before = 0;
using namespace std;
int main()
{

	cin >> length >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> now;
		a[i] = now - before;
		before = now;
	}
	a[n] = length - before;
	l = 1;
	if (n == m)
	{
		cout << length;
		return 0;
	}
	r = length / (n - m);
	while (l <= r)
	{
		int mid = (l + r) / 2, tmp,count = 0;

		for (int i = 0; i <= n; i++)
		{
			tmp = a[i];
			while (tmp < mid && i < n)
			{
				i++;
				tmp += a[i];
				count++;
			}
		}

		if (count > m)
		{
			r = mid - 1;
		}
		else {
			l = mid + 1;
        }
	}

	cout << r;


}

[TJOI2007] 路标设置

题目背景

B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。

题目描述

现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。

输入格式

第 \(1\) 行包括三个数 \(L,N,K\)，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。

第 \(2\) 行包括递增排列的 \(N\) 个整数，分别表示原有的 \(N\) 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 \([0,L]\) 内。

输出格式

输出 \(1\) 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。

样例 #1

样例输入 #1

1
2
101 2 1
0 101

样例输出 #1

1
51

提示

公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 \(50\) 或 \(51\) 个单位距离处，这样能达到最小的空旷指数 \(51\)。

\(50\%\) 的数据中，\(2 \leq N \leq 100\)，\(0 \leq K \leq 100\)。

\(100\%\) 的数据中，\(2 \leq N \leq 100000\), \(0 \leq K \leq100000\)。

\(100\%\) 的数据中，\(0 < L \leq 10000000\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
using namespace std;
int length, n, k, a[10000005], now, before = 0, r;
int main()
{
	cin >> length >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> now;
		a[i] = now - before;
		before = now;
		if (r<a[i])
		{
			r = a[i];
		}
	}
	a[n] = length - before;
	if (r<a[n])
	{
		r = a[n];
	}
	int l = 1, r = 100000000;
	if (k==0)
	{
		cout << r;
		return 0;
	}
	while (l<=r)
	{
		int mid = (l + r) / 2, count = 0, tep;
		for (int i = 0; i <=n ; i++)
		{
			tep = a[i];
			while (tep>mid)
			{
				count++;
				tep -= mid;
			}
		}
		if (count<=k)
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << l;
}

数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 \(A_{1\sim N}\)，现要将其分成 \(M\)（\(M\leq N\)）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段。

将其如下分段：

\[[4\ 2][4\ 5][1]\]

第一段和为 \(6\)，第 \(2\) 段和为 \(9\)，第 \(3\) 段和为 \(1\)，和最大值为 \(9\)。

将其如下分段：

\[[4][2\ 4][5\ 1]\]

第一段和为 \(4\)，第 \(2\) 段和为 \(6\)，第 \(3\) 段和为 \(6\)，和最大值为 \(6\)。

并且无论如何分段，最大值不会小于 \(6\)。

所以可以得到要将数列 \(4\ 2\ 4\ 5\ 1\) 要分成 \(3\) 段，每段和的最大值最小为 \(6\)。

输入格式

第 \(1\) 行包含两个正整数 \(N,M\)。

第 \(2\) 行包含 \(N\) 个空格隔开的非负整数 \(A_i\)，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

样例 #1

样例输入 #1

1
2
5 3
4 2 4 5 1

样例输出 #1

1
6

提示

对于 \(20\%\) 的数据，\(N\leq 10\)。

对于 \(40\%\) 的数据，\(N\leq 1000\)。

对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(M\leq N\)，\(A_i < 10^8\)， 答案不超过 \(10^9\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n)  for(int i=a;i<=n;i++)
const int N=1e6+100;
using ll=long long;
int a[N];
int sum;
int n;
int m;
bool check(int x)
{
	int cnt=1;
	int ans=0;
rep(i,1,n)
{
if(ans+a[i]>x)
{
	cnt++;
	ans=a[i];
}
else
{
	ans+=a[i];
}
}
return cnt>m;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int l = 0;
	rep(i, 1, n)
	{
		cin >> a[i];
		sum += a[i];
l=max(l,a[i]);
}
int r=sum;
int mid;
while(l+1<r)
{
	 mid=(l+r)/2;
	if(check(mid))
	{
		l=mid;
	}
	else
	{
		r=mid;
	}
}
if(!check(l))
{
	cout<<l;
}
else
{
	cout<<r;
}
}

银行贷款

题目描述

当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。

输入格式

三个用空格隔开的正整数。

第一个整数表示贷款的原值 \(w_0\)，第二个整数表示每月支付的分期付款金额 \(w\)，第三个整数表示分期付款还清贷款所需的总月数 \(m\)。

输出格式

一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 \(0.1\%\)。

数据保证答案不超过 \(300.0\%\)。

样例 #1

样例输入 #1

1
1000 100 12

样例输出 #1

1
2.9

提示

数据保证，\(1 \leq w_0, w\leq 2^{31}-1\)，\(1 \leq m\leq 3000\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;
int main()
{
	int loan, pay, month;
	double l = 0, r = 10 , mid, t;
	cin >> loan >> pay >> month;

	while (l<r)
	{
		mid = (l + r) / 2;
		if (r-l<0.0001)
		{
			
			break;
		}
		
		t = loan;
		for (int i = 0; i < month; i++)
		{
			t = t * (1 + mid) - pay;
		}
		if (t>0)
		{
			r = mid;
		}
		else if (t<0)
		{
			l = mid;
		}
		else
		{
			printf("%.1f", mid*100);
			return 0;
		}
	}
	printf("%.1f", mid * 100);
	return 0;
}

kotori的设备

题目背景

kotori 有 \(n\) 个可同时使用的设备。

题目描述

第 \(i\) 个设备每秒消耗 \(a_i\) 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 \(k\) 秒内消耗的能量均为 \(k\times a_i\) 单位。在开始的时候第 \(i\) 个设备里存储着 \(b_i\) 个单位能量。

同时 kotori 又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 \(p\) 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。

kotori 想把这些设备一起使用，直到其中有设备能量降为 \(0\)。所以 kotori 想知道，在充电器的作用下，她最多能将这些设备一起使用多久。

输入格式

第一行给出两个整数 \(n,p\)。

接下来 \(n\) 行，每行表示一个设备，给出两个整数，分别是这个设备的 \(a_i\) 和 \(b_i\)。

输出格式

如果 kotori 可以无限使用这些设备，输出 \(-1\)。

否则输出 kotori 在其中一个设备能量降为 \(0\) 之前最多能使用多久。

设你的答案为 \(a\)，标准答案为 \(b\)，只有当 \(a,b\) 满足 \(\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}\) 的时候，你能得到本测试点的满分。

样例 #1

样例输入 #1

1
2
3
2 1
2 2
2 1000

样例输出 #1

1
2.0000000000

样例 #2

样例输入 #2

1
2
1 100
1 1

样例输出 #2

1
-1

样例 #3

样例输入 #3

1
2
3
4
3 5
4 3
5 2
6 1

样例输出 #3

1
0.5000000000

提示

对于 \(100\%\) 的数据，\(1\leq n\leq 100000\)，\(1\leq p\leq 100000\)，\(1\leq a_i,b_i\leq100000\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//很好理解()
#include  <iostream>
using namespace std;
int n;
double p;
const int N=200000;
double a[N],b[N];
double lbound=0,rbound=1e10;
double sum=0;
int check(double ans){
	double q=p*ans;
	sum=0;
	for(int i=0;i<n;i++){
		if(a[i]*ans<=b[i]){
			continue;
		}
		sum+=(a[i]*ans-b[i]);
	}
	return sum<=q;
}
int main(){
	cin>>n>>p;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		sum+=a[i];
	}
	if(sum<=p){
		cout<<-1.000000<<'\n';
		return 0;
	}
	while(rbound-lbound>1e-6)
    {
		double mid=(lbound+rbound)/2;
		if(check(mid))
        {
			lbound=mid;	
		}
        else
        {
			rbound=mid;	
		}
	}
	cout<<lbound<<'\n';
}