Aotle

你所看到的惊鸿，都曾被平庸磨练

Aotle

二分查找算法考试复习(不仅仅是二分查找，还有一些水题)

单词排序

题目描述

小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，单词两两之间用一个空格分隔。

输入

输入包含两行。

第一行仅包括一个正整数N(0<N≤26)。

第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。

单个单词长度不超过1010。

输出

输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。

样例输入

1
2
4
city boy tree student

样例输出

1
boy city student tree

思路

水题，按照字典序排列后输出即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s[1015];
int main()
{
    int n;
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>s[i];
	}
	sort(s,s+n);
	for(int i=0;i<n;++i){
		cout<<s[i]<<' ';
	}
}

渊子赛马

题目描述

赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。 比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。 就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有 N(1<=n<=1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。

输入

输入有多组测试数据。 每组测试数据包括 3 行： 第一行输入 N。表示马的数量。 第二行有 N 个整型数字，即渊子的 N 匹马的速度。 第三行有 N 个整型数字，即对手的 N 匹马的速度。 当 N 为 0 时退出。

输出

若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出YES。 否则输出NO。

样例输入

1
2
3
4
5
6
7
5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0

样例输出

1
2
YES
NO

思路

先排序，遍历对手的马，找到刚好能打败对手的马，然后把这匹马标记（不能用了）num++，循环，最后判断num是不是大于n/2+1。

代码

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
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int s[1015];
int d[1015];
int flag[1015];
int main()
{
    int n;
	while(cin>>n&&n!=0){
		for(int i=0;i<n;++i){
			cin>>s[i];//我的马 
		}
		for(int i=0;i<n;++i){
			cin>>d[i];//对手的马 
		}
		sort(s,s+n);
		sort(d,d+n);
		int num=0;
		for(int i=0;i<n;++i){
			//遍历对手的马
			for(int j=0;j<n;++j){
				if(s[j]>d[i]&&flag!=0){
					num++;
					flag[j]=1;
					break;
				}
			} 
		}
		if(num>n/2+1)
		cout<<"YES"<<endl;
		else
		cout<<"NO"<<endl;
	}
}

区间第K小

题目描述

花花上算法课又偷偷摸鱼。她今天刚学会如何求解区间第k小的数，但是感觉没什么意思。于是她将题目稍稍改动了一下：对于一个长度为n的数列a来说，一共有n*(n+1)/2个子区间，对于数列a的每一个子区间，如果这个子区间的长度小于k，我们不管它，否则把该子区间的第k小的数加入新数列b（初始为空）。花花并不关心数列b里面的元素是什么，她只想知道新数列b中第k小的元素是多少。

例如，一个长度为4的数列a={5,3,4,9}，当k取3时只有三个子区间长度是>=3的：{5,3,4},{3,4,9}和{5,3,4,9}。分别提取各自的第3小的数加入b数列得到{5,9,5},其中第3小的数为9。

输入

第一行两个数n，k（1<=n, k<=1e5)意义见题目描述

第二行n个数表示数列a中的元素ai。(1<=ai<=1e9)

数据保证数列b中的元素个数不少于k个

输出

输出一个数，表示数列b中的第k小的数

样例输入

1
2
4 3
5 3 4 9

样例输出

1
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
//说实话，没看懂这个代码，可能是我太菜了吧
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int n, k;
long long max_position(int x)
{
    long long result = 0;             
    int l = 0, r = -1, num = 0;
    while (r < n)
    {
        if (num < k)                   
        {
            if (a[r + 1] <= x)num++;
            r++;
        }
        else
        {
            result += n - r;
            if (a[l] <= x)num--;
            l++;
        }
    }
    return result;
}
int main()
{
    cin >> n >> k;
    int*b=new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    int len = unique(b, b + n) - b;    
    int l = 0, r = len - 1;
    int ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        long long ret = max_position(b[mid]);
        if (ret >= k)        
        {
            ans = b[mid];
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

元素整除问题

题目描述

输入20个整数，输出其中能被数组中其它元素整除的那些数组元素。

输入

输入20个整数

输出

按输入顺序输出符合要求的数字，每行输出一个整数。

样例输入

1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
4
6
8
9
10
12
14
15
16
18
20
21

代码

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
#include <bits/stdc++.h>
using namespace std;
int a[20];
int b[20];
int main()
{
    for (int i = 0; i < 20;++i){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + 20);
    for (int i = 0; i < 20;++i){
        bool flag = false;
        for (int j = 0; j < 20;++j){
            if(a[i]>b[j]){
                if(a[i]%b[j]==0){
                    flag = true;
                    break;
                }
            }
            else{
                break;
            }
        }
        if(flag)
            cout << a[i] << endl;
    }

        return 0;
}

内部收益率

题目描述

img

输入

img

输出

对于每组数据，输出仅一行，即项目的IRR，四舍五入保留小数点后两位。

样例输入

1
2
3
4
5
1
-1 2
2
-8 6 9
0

样例输出

1
2
1.00
0.50

代码

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
#include<iostream>
#include <iomanip>
using namespace std;
int main()
{
    int n, f, CF[12];
    while (cin>>n && n != 0)
    {
        cin >> f;
        double mid, high = 10000, low = -1, r, k, sum;
        for (int i = 0; i < n; i++)
            cin >> CF[i];
        while (high - low > 1.0e-6)    
        {
            mid = (high + low) / 2; 
            k = 1;
            sum = 0;
            for (int j = 0; j < n; j++)
            {
                k *= (1.0 / (1 + mid)); 
                sum += CF[j] * k;  
            }
            if (sum + f > 0)
                low = mid;
            else
                high = mid;
        }
        cout << fixed << setprecision(2) << mid << endl;
    }
    return 0;
}

问题 J: 奶牛的聚会

题目描述

农历新年马上就要到了，奶牛们计划举办一次聚会庆祝新年的到来。但是，奶牛们并不喜欢走太远的路，这会给他们的聚会带来消极情绪，当一头奶牛的消极指数为Wi，他参加聚会所需行走的距离为si，那么他就会给聚会带来Si3*Wi的消极情绪。所有奶牛所在位置都在一条直线上，已知所有奶牛的坐标和消极指数，求如何确定聚会地点，使得所有奶牛给聚会带来的消极情绪之和最小，输出消极情绪之和的最小值。

输入

第一行包含一个整数 Ca(Ca<=20) ，表示有 Ca 组测试数据。

对于每组测试数据：第一行包含一个整数n(1<=n<=50000) ，表示奶牛的数量。接下来 n 行每行包含两个浮点数Si和wi (-106<=Si<=106, 0<Wi<15)。

输出

对于每组测试数据，输出 “Case #c: ans” ，其中c表示测试数据编号，ans表示消极情绪之和的最小值，结果四舍五入为一个整数。

样例输入

1
2
3
4
5
6
7
1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2

样例输出

1
Case #1: 300

思路

三分查找法确定消极情绪之和最小的位置，结合注释应该不难理解。

代码

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
#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
const int maxn = 50010;
double Si[maxn], wi[maxn];
int n, Ca;
//计算聚会位置在pos时的消极情绪之和
double ans(double pos)
{
    double sum = 0;
    for (int i = 0; i < n; i++)
    {
        //计算每个奶牛距离聚会位置的距离(非负)
        double dist = Si[i] - pos;
        if (dist < 0)
            dist = -dist;
        sum += pow(dist, 3) * wi[i];
    }
    return sum;
}
int main()
{
    cin >> Ca;
    for (int i = 1; i <= Ca; i++)
    {
        cin >> n;
        for (int j = 0; j < n; j++)
        {
            cin >> Si[j] >> wi[j];
        }
        //找到坐标位置最小的奶牛
        double low = Si[0];
        for (int k = 0; k < n; k++)
            if (Si[k] < low)
                low = Si[k];
        //找到坐标位置最小的奶牛
        double high = Si[0];
        for (int l = 0; l < n; l++)
            if (Si[l] > high)
                high = Si[l];
        //三分查找法确定最终位置
        while (high - low > 1e-7)
        {
            double m1 = (high + low) / 2.0;
            double m2 = (m1 + high) / 2.0;
            if (ans(m1) > ans(m2))
                low = m1;
            else
                high = m2;
        }
        cout << "Case #" << i << ": " << ll(ans(low) + 0.5) << endl;
    }
    return 0;
}

问题 E: 光合作用

题目描述

蒜头是个爱学习的孩子，他总喜欢在生活中做一些小实验，这次蒜头想研究一下光合作用。蒜头的实验材料有如下几样：神奇的种子，普通的纸箱和一些光源。一开始，蒜头将种子均匀的种在了箱子底部，你可以将其看成 X 轴，种子的位置为 X 轴上的点。然后蒜头用纸板将箱子盖住，并在纸板上安装了一些光源（具体见图，顶上的为光源，光源两边与顶部的夹角都为45度，黄色部分为光照，绿色的为植物。）。神奇的种子会在有光的情况下一直向上生长直到没光为止。现在蒜头想知道当实验结束时每颗种子的高度是多少？

输入

第一行输入一个整数 T，表示测试数据的组数。

每组数据的第一行是三个整数 n,m,h(1<=n,m<=1e5,0<=m<=1e5,1<=h<=1e4),n表示种子数(编号为1,2…n)，m表示光源数,h 表示箱子的高度。

接下来m行，每行一个整数Xi表示第i个光源在顶部的位置。

输出

对于每组测试数据，请输出n行，每行一个数表示第i颗种子的最终高度。

样例输入

1
2
3
4
5
6
7
8
2
7 1 2
4
4 4 1
1
2
3
4

样例输出

1
2
3
4
5
6
7
8
9
10
11
0
0
1
2
1
0
0
1
1
1
1

思路

二分法

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
/*********************************************************************************************
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
********************************************************************************************/
const int maxn = 1e5 + 5;
int x[maxn];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, m, h;
        cin >> n >> m >> h;
        for (int i = 1; i <= m; i++)
        {
            cin >> x[i];
        }
        sort(x + 1, x + m + 1);
        for (int i = 1; i <= n; i++)
        {
            int ans = 0;
            int cnt = lower_bound(x + 1, x + m + 1, i) - x;
            if (cnt == 1 && m != 0)
            {
                ans = max(ans, h - x[cnt] + i);
            }
            else if (cnt == m + 1 && m != 0)
            {
                ans = max(ans, h - i + x[cnt - 1]);
            }
            else if (m != 0)
            {
                ans = max(0, max(h - i + x[cnt - 1], h - x[cnt] + i));
            }
            cout << ans << endl;
        }
    }
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://aotle.top/2020/10/31/erfenchazhao1/

评论