开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构与stl专训 -> 正文阅读

[数据结构与算法]数据结构与stl专训

数据结构与stl

—————————————————————————————————————————————

A. 最小函数值(minval)

题目描述
有n个函数，分别为F1、F2…Fn 。定义
$F_i(x) = A_ix^2 + B_i x + C_i ( x \in N * )$
给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。

输入格式
第一行输入两个正整数n和m。 n,m≤10000
以下行每行三个正整数，其中第i行的三个数分别为Ai、Bi和Ci。

输出格式
将这n个函数所有可以生成的函数值排序后的前m个元素。这m个数应该输出到一行，用空格隔开。

数据范围 在这里插入图片描述
样例输入

样例输出

9 12 12 19 25 29 31 44 45 54

代码
stl：优先队列小根堆

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

priority_queue <int, vector<int>, greater<int> > q;
//重载运算符 小根堆优先队列
int n, m;
int a, b, c;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        for (int j = 1; j <= 600; j++) {//卡常
            int f = a * j * j + b * j + c;
            q.push(f);
        }
    }
    for (int i = 0; i < m; i++) {
        printf("%d ", q.top());
        q.pop();
    }
}

划重点：

priority_queue <int, vector<int>, greater<int> > q;

—————————————————————————————————————————————

B. 看病

题目描述
有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判断接下来谁可以去看病。

输入格式
第一行输入n，表示有n个操作。
对于每个操作，首先输入push或pop。
push的情况，之后会输入ai 和 bi，分别表示患者姓名和患者病情优先级。
pop后面没有输入，但需要你输出。

输出格式
对于pop的操作，输出此时还在排队人中，优先级最大的患者姓名和优先级。
表示他可以进去看病了。
如果此时没人在排队，那么输出”none”，具体可见样例。

样例输入

7
pop
push bob 3
push tom 5
push ella 1
pop
push zkw 4
pop

样例输出

none
tom 5
zkw 4

代码
优先队列结构体排序

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

int n,cnt;
struct node{
	string name;
	int lev;
	bool operator <(const node &x) const {	return x.lev >lev;	}
};
priority_queue<node>q;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		if(s=="push"){
			node t;
			cin>>t.name;
			cin>>t.lev;
			q.push(t);
		}
		else if(!q.empty() &&s=="pop"){
			cout<<q.top().name<<" "<<q.top() .lev<<endl;
			q.pop() ;
		}
		else
			cout<<"none"<<endl;
	}
}

—————————————————————————————————————————————

C. 小明的账单

题目描述
小明在一次聚会中，不慎遗失了自己的钱包，在接下来的日子，面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下，老板最终同意延缓账单的支付时间。可老板又提出，必须从目前还没有支付的所有账单中选出面额最大和最小的两张，并把他们付清。还没有支付的账单会被保留到下一天。请你帮他计算出支付的顺序。

输入格式
第1行：一个正整数N(N≤15,000)，表示小明补办银联卡总共的天数。
第2行到第N+1 行：每一行描述一天中收到的帐单。先是一个非负整数M≤100，表示当天收到的账单数，后跟M个正整数（都小于1,000,000,000），表示每张帐单的面额。
输入数据保证每天都可以支付两张帐单。

输出格式
输出共N 行，每行两个用空格分隔的整数，分别表示当天支付的面额最小和最大的支票的面额。

样例输入

样例输出

代码
stl：multiset 可重复集合
set 自动排序由小到大

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

multiset<int> st;
int n,m;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&m);
		for(int j=1;j<=m;j++){
			int t;
			scanf("%d",&t);
			st.insert(t); 
		}
		printf("%d ",*st.begin());
		st.erase(st.begin());
		printf("%d\n",*--st.end() );
		st.erase(--st.end()); 		
	}
}

—————————————————————————————————————————————

D. 鱼塘钓鱼(fishing）

题目描述
有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：
鱼塘编号　　　　　　　　　　　　　　　　　　　　　1　　2　　3　　4　　5
每1分钟能钓到的鱼的数量（1…1000）　　　　　　　10 　14 　20　 16 　9
每1分钟能钓鱼数的减少量（ 1…100 ）　　　　　　　　2　　4　　6　　5　　3
当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）　3　　5　　4　　4
即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……
给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。

输入格式

输出格式

样例输入

5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14

样例输出

代码

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

struct node {
    int sum, num;
    bool operator<(node x) const { return sum < x.sum; }
};

priority_queue<node> q;
priority_queue<int> res;
int n, t;
int a[500], del[500], d[500];
int ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &del[i]);
    }
    for (int i = 1; i < n; i++) {
        scanf("%d", &d[i]);
    }
    scanf("%d", &t);

    int dis = 0, t_nw;
    for (int i = 1; i <= n; i++) {
        t_nw = t - dis;
        for (int j = 1; j <= i; j++) {
            q.push({ a[j], j });
        }
        while (t_nw > 0 && q.top().sum > 0) {
            node f = q.top();
            q.pop();
            ans += f.sum;
            f.sum -= del[f.num];
            q.push(f);
            t_nw--;
        }
        res.push(ans);
        ans = 0;
        dis += d[i];
    }
    if (!res.empty())
        printf("%d", res.top());
    else
        printf("0\n");
}

—————————————————————————————————————————————

E. 家庭问题(family)

题目描述
有n个人，编号为1,2,……n，另外还知道存在K个关系。一个关系的表达为二元组（α，β）形式，表示α，β为同一家庭的成员。
当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？
例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(4,5)
此时，6个人组成三个家庭，即：｛1,2,3｝为一个家庭，｛4,5｝为一个家庭，｛6｝单独为一个家庭，第一个家庭的人数为最多。

输入格式
第一行为n,k二个整数（1≤n≤100）（用空格分隔）;
接下来的k行，每行二个整数（用空格分隔）表示关系。

输出格式
二个整数（分别表示家庭个数和最大家庭人数）。

样例输入

样例输出

3  3

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

int n, k, cnt;
vector<int> q[205];
queue<int> qq;
priority_queue<int> a;
bool v[205];

void bfs(int x) {
    int num = 0;
    while (!qq.empty()) {
        int f = qq.front();
        qq.pop();
        if (!q[f].empty())
            for (int i = 0; i < q[f].size(); i++) {
                int t = q[f][i];
                if (v[t] == 0) {
                    v[t] = 1;
                    qq.push(t);
                    num++;
                }
            }
  		}
    a.push(num + 1);
}

int main() {
    scanf("%d%d", &n, &k);
    //	printf("%d %d\n",n,k);

    for (int i = 1; i <= k; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        //		printf("%d %d\n",a,b);
        q[a].push_back(b);
        q[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (v[i] == 0) {
            //			printf("i:%d\n",i);
            v[i] = 1;
            qq.push(i);
            bfs(i);
            cnt++;
        }
    }
    printf("%d %d", cnt, a.top());
}

—————————————————————————————————————————————

F. 连通块

题目描述
一个n * m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。

输入格式
第一行两个整数n,m(1≤n,m≤100)，表示一个n * m的方格图。
接下来n行，每行m个整数，分别为0或1，表示这个格子是黑色还是白色。

输出格式
一行一个整数ans，表示图中有ans个黑色格子连通块。

样例输入

样例输出

代码

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

struct node {
    int x, y;
};
int n, m, cnt;
int a[200][200];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
bool v[200][200];

queue<node> q;

void bfs(int x, int y) {
    while (!q.empty()) {
        node f = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            node t;
            t.x = f.x + dx[i];
            t.y = f.y + dy[i];
            if (t.x >= 1 && t.x <= n && t.y >= 1 && t.y <= m && a[t.x][t.y] != 0 && !v[t.x][t.y]) {
              
                v[t.x][t.y] = 1;
                q.push(t);
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            a[i][j] = s[j - 1] - '0';
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] != 0 && v[i][j] == 0) {
                node t = { i, j };
                q.push(t);
                v[i][j] = 1;
                bfs(i, j);
                cnt++;
            }
        }
    }

    printf("%d", cnt);
}

—————————————————————————————————————————————

G. 产生数

题目描述
给出一个整数n（n≤2000）和k个变换规则（k≤15）。规则：
① 1个数字可以变换成另1个数字；
② 规则中，右边的数字不能为零。
例如：n=234，k=2规则为
2 → 5
3 → 6
上面的整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564共4种不同的产生数。
求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。

输入格式
n
k
x1 y1
x2 y2
… …
xn yn

输出格式
格式为一个整数（满足条件的整数个数）。

样例输入

样例输出

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

string n;
int k, ans = 1;
vector<int> a[30];
queue<int> q;
bool v[30];
int tmp[5];

int bfs(int x) {
    int cnt = 1;
    q.push(x);

    while (!q.empty()) {
        int f = q.front();
        q.pop();
        for (int i = 0; i < a[f].size(); i++) {
            int t = a[f][i];
            if (v[t] == 0) {
                v[t] = 1;
                cnt++;
                q.push(t);
            }
        }
    }
    return cnt;
}

int main() {
    cin >> n;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
    }
    int c = 1;
    for (int i = 0; i < n.size(); i++) {
        memset(v, 0, sizeof(v));
        int t = n[i] - 48;
        v[t] = 1;
        tmp[c++] = bfs(t);
    }

    for (int i = 1; i < c; i++) {
        //		printf("%d ",tmp[i]);
        ans *= tmp[i];
    }
    printf("%d", ans);
}

—————————————————————————————————————————————

H. 最少步数

题目描述
在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。

输入格式 A、B两点的坐标。

输出格式 最少步数。

样例输入

12 16
18 10

样例输出

8 
9

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

struct node {
    int x, y, dis;
};
queue<node> q;
node a, b;
bool v[200][200];
int dx[12] = { -2, -1, -1, -2, 2, 1, -1, -2, 2, 2, -2, -2 };
int dy[12] = { -1, -2, 2, 1, -1, -2, 2, 1, 2, -2, 2, -2 };
int cnt1, cnt2;

void bfs(int x, int y) {
    while (!q.empty()) {
        node f = q.front();
        q.pop();
        for (int i = 0; i < 12; i++) {
            node t;
            t.x = f.x + dx[i];
            t.y = f.y + dy[i];
            t.dis = f.dis + 1;
            if (t.x == 1 && t.y == 1) {
                printf("%d\n", t.dis);
                v[t.x][t.y] = 1;
                return;
            }
            if (t.x >= 1 && t.y >= 1 && v[t.x][t.y] == 0) {
                //				printf("%d %d\n",t.x,t.y);
                v[t.x][t.y] = 1;
                q.push(t);
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
    //	printf("%d %d %d %d \n",a.x,a.y,b.x,b.y);
    q.push(a);
    v[a.x][a.y] = 1;
    a.dis = 0;
    bfs(a.x, a.y);

    memset(v, 0, sizeof(v));
    while (!q.empty()) q.pop();

    q.push(b);
    v[b.x][b.y] = 1;
    b.dis = 0;
    bfs(b.x, b.y);
}

—————————————————————————————————————————————

I. 计算(calc)

题目描述
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)

输入格式 共1行，为一个算式。

输出格式 共1行，就是密码。

样例输入

1+(3+2)*(7^2+6*9)/(2)

样例输出

代码

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
using namespace std;

stack<int> s1;
stack<char> s2;

string s;

bool num_jd(char x) {
    if (x - '0' >= 0 && x - '0' <= 9)
        return 1;
    return 0;
}

int num_tr(int st, int ed, int n) {
    int t = 0, c = 0;
    for (int i = ed; i >= st; i--, c++) {
        t += (s[i] - '0') * pow(10, c);
    }
    return t;
}

void calc() {
    char c = s2.top();
    s2.pop();
    int b = s1.top();
    s1.pop();
    int a = s1.top();
    s1.pop();
    //	printf("a:%d  c:%c  b:%d\n",a,c,b);
    switch (c) {
        case '+':
            s1.push(a + b);
            break;
        case '-':
            s1.push(a - b);
            break;
        case '*':
            s1.push(a * b);
            break;
        case '/':
            s1.push(a / b);
            break;
        case '^':
            s1.push(pow(a, b));
            break;
        default:
            break;
    }
    //	printf("calc:%d\n",s1.top() );
}

bool judge(char x) {
    char c = s2.top();
    if ((x == '+' || x == '-') && (c != '('))
        return 1;
    if ((x == '*' || x == '/') && (c == '^' || c == '*' || c == '/'))
        return 1;
    if (x == '^' && c == '^')
        return 1;
    return false;
}

// void text_s1(){
//	printf("s1:");
//	while(!s1.empty() ){
//		printf("%d ",s1.top() ); s1.pop() ;
//	}
//	printf("\n");
//}
//
// void text_s2(){
//	printf("s2:");
//	while(!s2.empty() ){
//		printf("%c ",s2.top() ); s2.pop() ;
//	}
//	printf("\n");
//}

int main() {
    cin >> s;
    s = '(' + s + ')';

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            s2.push(s[i]);
        } else if (s[i] == ')') {
            while (s2.top() != '(') {
                calc();
            }
            s2.pop();
        } else if (num_jd(s[i])) {
            int j = i;
            while (num_jd(s[i])) {
                i++;
            }
            int num = i - j;
            int t = num_tr(j, i - 1, num);
            //			printf("%d \n",t);
            s1.push(t);
            i--;
        } else {
            while (judge(s[i])) {
                calc();
            }
            s2.push(s[i]);
        }
    }
    //	text_s1();
    printf("%d", s1.top());
}