$\color{Orange}{题目1：1000名求前30%}$

题目标签

堆排序

题目描述

排序问题：1000个成绩输出前30%。

输入样例：

输入10个

输出样例：

输出3个

原题链接

参考代码

#include <cstdio>
#include <algorithm>
using namespace std;
 //给定十个元素输出最大的前三个，元素从下标1开始存储
int heap[11] = {0, 3, 1, 2, 6, 5, 4, 9, 8, 7, 10};
int n = 10;      //元素个数

//对heqap数组在loe和high范围内进行调整
//low为父节点，high一般为堆的最后一个元素下标
void downAdjust(int low, int high){
    int i = low, j = i * 2;     //i为调整节点，j为左孩子
    while(j <= high){           //如果存在左孩子
        if(j + 1 <= high && heap[j + 1] > heap[j]){     //如果右孩子存在，且值大于左孩子
            j = j + 1;          //j来存储右孩子下标
        }
        //孩子中最大的权值大于要调整的节点
        if(heap[j] > heap[i]){
            swap(heap[j], heap[i]);
            i = j;          //继续调整以j为父节点的子树
            j = i * 2;
        }
        else
            break;
    }
} 
//建树
void createHeap(){
    for(int i = n / 2; i >= 1; i--){        //i从第一个非叶节点开始，直到根结点
        downAdjust(i, n);
    }
} 
void heapSort(){
    createHeap();   //建堆
    printf("%d", heap[1]);    //输出第一个最大值
    for(int i = n; i > 8; i--){     //倒着枚举，直到输出符合题目要求的数量
        swap(heap[i], heap[1]);     //交换heap[i]与堆顶
        downAdjust(1, i - 1);       //调整堆顶
        printf(" %d", heap[1]);     //调整过后，堆顶元素为最大值，输出
    }
    printf("\n");
}

int main(){
    heapSort();
    return 0;
}

$\color{Orange}{题目2：二叉树最大叶子间距}$

题目标签

二叉树

题目描述

二叉树问题。比如节点是ABCDE编号是01234，给出每个左右子树的编号。求最大叶子间距。

输入样例1

3
1 2
-1 -1
-1 -1

输出样例1：

2

输入样例2

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

输出样例2：

4

原题链接

参考代码

#include <stdio.h>
const int maxn=100;
struct node{
    int lchild,rchild;
}Node[maxn];
int maxd;  //全局变量记录最大叶子间距
//求最大叶子间距
int maxDistance(int root,int &maxd){
    if(root==-1)
        return -1;
    int lefth=maxDistance(Node[root].lchild,maxd)+1;
    int righth=maxDistance(Node[root].rchild,maxd)+1;
    if(lefth+righth>maxd){
        maxd=lefth+righth;
    }
    return lefth>righth?lefth:righth;   //返回的是当前结点为根时的深度
}
int main(){
    int n,left,right;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&left,&right);
        Node[i].lchild=left;
        Node[i].rchild=right;
    }
    maxDistance(0,maxd);
    printf("%d\n",maxd);
    return 0;
}

$\color{Orange}{题目3：字符串的重复输出}$

题目标签

多一道水题，少一个玉玉

题目描述

给一个字符串比如ABC 再给一个整数比如3输出AAABBBCCC就行了。

原题链接

参考代码

#include <string>
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    string str;
    getline(cin, str);
    int n;
    cin >> n;
    for(int i = 0; i < str.size(); i++){
        for(int j = 0; j < n; j++){
            printf("%c", str[i]);
        }
    }
    printf("\n");
    return 0;
}