洛谷题单--入门

大象喝水

题目描述

一只大象口渴了，要喝 $20$ 升水才能解渴，但现在只有一个深 $h$ 厘米，底面半径为 $r$ 厘米的小圆桶 （$h$ 和 $r$ 都是整数）。问大象至少要喝多少桶水才会解渴。

输入格式

输入有一行：包行两个整数，以一个空格分开，分别表示小圆桶的深 $h$ 和底面半径 $r$，单位都是厘米。

输出格式

输出一行，包含一个整数，表示大象至少要喝水的桶数。

样例 #1

样例输入 #1

23 11

样例输出 #1

3

提示

数据规模与约定

对于全部的测试点，保证 1<=h<=500,1<=r<=100。

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int main()
{
    int h,r;
    double m;
    cin>>h>>r;
    m=h*r*r*acos(-1);

    cout<<ceil(20000/m)<<endl;

    return 0;
}

学习心得

这里学了两个函数，一个是acos(-1),可以表示数学中的Π，另一个函数是
ceil()函数，表示向上取整。

【深基9.例4】求第 k 小的数

题目描述

输入 n（1 <= n < 5000000$ 且 n 为奇数）个数字 a_i（1 <= a_i < {10}^9），输出这些数字的第 k 小的数。最小的数是第 0 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define  num 5000005
int a[num];
int n,k;
int quicksort(int left, int right)
{
    int mid=a[left];
    while(left<right)
    {
        while(left<right&&mid<=a[right])
            right--;
        a[left]=a[right];
        while(left<right&&a[left]<=mid)
            left++;
        a[right]=a[left];
    }
    a[left]=mid;
    return left;
}
int find_(int left,int right,int k)
{
    int tem=quicksort(left,right);
    if(k==tem)
        printf("%d",a[k]);
    else if(k-1<tem)
        find_(left,tem-1,k);
    else
        find_(tem+1,right,k);
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    find_(0,n-1,k);


}

方法2 nth_element

#include<bits/stdc++.h>
using namespace std;
int x[5000005],k;
int main()
{
	int n;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",&x[i]);
	nth_element(x,x+k,x+n);//简短又高效
	printf("%d",x[k]);
}

学习心得

这里用sort函数会超时，体会到sort函数不是什么情况下都能用的，这里用了分治的思想，用快速排序，将第m小找出来，如果符合，则输出，不符合，就会省去前面一半或后面一半，降低了时间复杂度。

宇宙总统

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 $n$，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

输出格式

共两行，第一行是一个整数 $m$，为当上总统的人的号数。

第二行是当上总统的人的选票。

样例 #1

样例输入 #1

5
98765
12365
87954
1022356
985678

样例输出 #1

4
1022356

提示

票数可能会很大，可能会到 $100$ 位数字。

1<=n<=20

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n;
string a[105];
int num;
int length;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
         cin>>a[i];
         if(length<a[i].length())
         {
             num=i;
             length=a[i].length();
         }
         else if(length==a[i].length())
         {
             int k=0;
             while(1)
             {
                 if(a[i][k]-a[num][k]>0)
                 {
                     num=i;
                     length=a[i].length();
                     break;
                 }
                 else if(a[i][k]-a[num][k]<0)
                    break;
                 else k++;
             }
         }

    }
    cout<<num+1<<endl;
    cout<<a[num]<<endl;
}

大佬代码

include<iostream>
include<cstring>  
using namespace std; int main(){
int n,num;  
char a[201],max[201]="";
cin>>n;
for(int i=1;i<=n;i++){                      
    cin>>a;  
    if((strlen(max)<strlen(a))||(strlen(a)==strlen(max)&&strcmp(max,a)<0)){//若a的长度==max的长度，再用strcmp比较  
        strcpy(max,a);  
        num=i;  
    }  
}
cout<<num<<endl;  
puts(max);//输出
return 0; // 程序再见！
}

学习心得

strcpy()函数是复制字符串的函数，strcmp函数是比较每个字符串的大小，从第一个字符开始比较。