Polaris-hzn8

跳石头 原题链接：http://oj.haizeix.com/problem/394 一年一度的 “ 跳石头 ” 比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。 输入： 第一行包含三个整数 L, N , M ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L ≥ 1 且 N ≥ M ≥ 0 。 接下来 N 行，每行一个整数，第 i 行的整数 Di （0 < Di < L），表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。 输出： 一个整数，即最短跳跃距离的最大值。 样例： 12345625 5 2 2111417 21 14 1.思路 2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>using namespace std;int ll, n, m, num[50005], rawl = 1000000000;int func(int x) { int cnt = 0, last = 0; for (int i = 1; i <= n + 1; ++i) { if (num[i] - last < x) { cnt++; } else { last = num[i]; } } return cnt;}int bs() { int l = rawl, r = ll; while (l != r) ...

原木切割 原木切割（整数二分） 二分答案（用答案进行切分）应用满足条件：①具有左右边界、②数据具有单调性 二分答案（答案需要是单调的）就是用函数替代数组，二分的本质是删掉不存在答案的区间 原题链接：http://oj.haizeix.com/problem/390 某林业局现在 N 根原木，长度分别为 Xi ，为了便于运输，需要将他们切割成长度相等的 M 根小段原木（只能切割成整数长度，可以有剩余），小段原木的长度越大越好，现求小段原木的最大长度。 例如，有 3 根原木长度分别为 6,15,22，现在需要切成 8 段，那么最大长度为 5。 输入： 第一行两个整数 N, M 。（1 ≤ N ≤ 100,000，1 ≤ M ≤ 100,000,000） 接下来 N 行，每行一个数，表示原木的长度 Xi 。（1≤ Xi ≤100,000,000） 输出： 输出小段原木的最大长度， 保证可以切出 M 段。 样例： 12343 861522 15 1.解题思路 根据每一个二分答案长度num[i]，利用fun()函数进行计算，求出其对应的能切出木头的段数 根据当前分出的段数s与题目给定需要切出的段数m进行比较，从而调整左右指针 当左右指针逼近到一定范围时，表示最佳答案已经找到、 判断二分的特殊类型为10类型 2.代码实现二分答案（整数二分）即用func()函数现求函数值，替代二分查找中在数组中进行二分操作 输入数据，并动态更新二分答案的右边界 套用二分的特殊10类型相关模型进行处理 根据临时长度mid与func()函数求出，原木能够切出的段数 比较mid切出的段数与给定需要切出的段数进行比较，以此调整左右指针 当左右指针逼近到一定范围，即找到最佳答案 输出bs()二分函数最后返回的结果 1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>using namespace std;int n, m, num[100005], rawr;//求出当长度为mid时能切出的段数int func(int x) { int t = 0; for (int i = 0; i < n; ++i) { ...

暴躁的程序员 原题链接：http://oj.haizeix.com/problem/389 某公司的程序猿每天都很暴躁，因为他们每个人都认为其他程序猿和自己风格不同，无法一同工作。 当他们的工位的编号距离太近时，他们可能会发生语言甚至肢体冲突，为了尽量避免这种情况发生。现在公司打算重新安排工位，因为有些关系户的工位是固定的，现在只有一部分工位空了出来： 现在有 N 个程序猿需要分配在 M 个工位中，第 i 个工位的编号为 Xi，工位编号各不相同，现在要求距离最近的两个程序猿之间的距离最大，求这个最大距离是多少? Xi 和 Xj 工位之间距离为|Xi −Xj|。 输入： 输入共 M+1行，第一行两个整数 M, N（2 ≤ N ≤ M ≤ 100,000） 接下来 M 行，每行一个数表示剩余的工位的编号。 输出： 输出距离最近的两个程序猿之间的最大距离。 样例： 1234565 312849 13 1.解题思路 根据每一个二分答案长度num[i]，利用fun()函数进行计算，求出其对应的能够安排的程序员人数 根据当前能够分的人数s与题目给定需要分配的人数m进行比较，从而调整左右指针 当左右指针逼近到一定范围时，表示最佳答案已经找到 2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940#include<iostream>#include<algorithm>using namespace std;int n, m, num[100005];int func(int x) { int t = 1, last = num[0]; for (int i = 1; i < n; ++i) { if (num[i] - last >= x) { ++t; last = num[i]; } } return t;}int bs() { int l = 1, r = num[n - 1] - num[0]; while (l != r) { ...

切绳子 切绳子（小数二分） 原题链接：http://oj.haizeix.com/problem/393 有 N 条绳子，它们的长度分别为 Li 。如果从它们中切割出 K 条长度相同的绳子，这 K 条绳子每条最长能有多长？ 答案保留到小数点后 2 位（直接舍掉 2 位后的小数）。 输入： 第一行两个整数 N 和 K，接下来 N 行，描述了每条绳子的长度 Li 。 输出： 切割后每条绳子的最大长度，保证答案大于零。 样例： 123454 118.027.434.575.39 12.00 1.思路①整数二分与小数二分的不同点、②保留两位小数直接舍去的两种方法 2.代码实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<iostream>#include<cmath>#include<cstdio>using namespace std;int n, m;double num[10005], mmax;int func(double x) { int cnt = 0; for (int i = 0; i < n; ++i) { cnt += num[i] / x; } return cnt;}double bs() { double l = 0, r = mmax; //当差值大于预设精度则一直求解 while(fabs(l - r) > 0.00005) { double mid = (l + r) / 2; //根据mid值确定能够切出的绳子数量 int s = func(mid); if (s >= m) { l = mid; } else { r = mid; } } return r;}int main() { cin >> n ...

sort使用 一、简单排序1.基础12345678910111213141516171819202122//1.sort顺序排序：默认从小到大排序#include <iostream>#include <algorithm>using namespace std;int main(){ int num[55] = {0}; num[0] = 9; num[1] = 2; num[2] = -5; num[3] = 5; num[4] = 7; num[5] = 22; //使用sort函数对下标为(0, 5)数字的区间进行排序 sort(num, num + 6); for(int i = 0; i < 6; ++i){ cout << num[i] << endl; } cout << endl; return 0;} 2.仿函数12345678910111213141516171819202122//2.sort逆序排序：利用C++中的greater<int>()函数实现#include <iostream>#include <algorithm>using namespace std;int main(){ int num[55] = {0}; num[0] = 9; num[1] = 2; num[2] = -5; num[3] = 5; num[4] = 7; num[5] = 22; //重点:利用C++中的greater<int>()函数进行从大到小的排序 sort(num, num + 6, greater<int>()); for(int i = 0; i < 6; ++i){ cout << num[i] << endl; } cout << edl; return 0;&# ...

大统领投票 原题链接：http://oj.haizeix.com/problem/380 第一届地球大统领开始选拔，全地球的所有生物都积极参与投票，现在已知得票结果，请输出新当选的得票数最多的地球大统领的编号和得票数。 输入：输入第一行为一个整数 N 表示参选生物数。（1 ≤ N ≤ 100）接下来 N 行，每行一个整数，表示第 i 名参选生物的票数。票数不会超过 1000位。 输出： 输出得票数最多的生物的编号和票数。 样例： 1234312345679912345678913245678912345678911111111111111 122123456789132456789123456789 思路： 定义一个结构体包含某生物的编号与票数，使用sort方法对结构体排序后输出,时间复杂度: $O(nlogn)$ 遍历一遍所有生物，动态更新票数多的答案即可，时间复杂度: $O(n)$ 12345678910111213141516171819202122232425262728293031#include <iostream>#include <algorithm>#include <string>using namespace std;struct node{ int num; string score;};//当票数长度相同时，C++中已经重载了小于号可以直接使用进行字典顺序排序bool cmp(const node &a, const node &b){ if(a.score.size() == b.score.size()){ return a.score > b.score; } return a.score.size() > b.score.size();};node bio[105];int main(){ int n; cin >> n; for(int i = 1; i <= n; ++i){ cin >> bio[i].score; bio[i].num = i;
...

谁拿了最多奖学金 原题链接：http://oj.haizeix.com/problem/381 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 院士奖学金，每人 8000 元，期末平均成绩高于 80 分（>80），并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得； 五四奖学金，每人 4000 元，期末平均成绩高于 85 分（>85），并且班级评议成绩高于 80 分（>80）的学生均可获得； 成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（>90）的学生均可获得； 西部奖学金，每人 1000 元，期末平均成绩高于 85 分（>85）的西部省份学生均可获得； 班级贡献奖，每人 850 元，班级评议成绩高于 80 分（>80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高。 输入： 第一行是 1 个整数 N（1 ≤ N ≤ 100），表示学生的总数。 接下来的 N 行每行是一位学生的数据，从左向右依次是姓名、期末平均成绩、班级评议成绩、是否是学生干部、是否是西部省份学生、以及发表的论文数。 是否是学生干部和是否是西部省份学生分别用 1 个字符表示，Y 表示是，N 表示不是；发表的论文数是 0 到 10 的整数。 输出： 包括 3 行。 第 1 行是获得最多奖金的学生的姓名。 第 2 行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。 第 3 行是这 N 个学生获得的奖学金的总数。 样例： 123454YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1 123ChenRuiyi900028700 思路： 构造student结构体，包含编号num、姓名name、期末平均成绩avg、班级评议成绩cla_avg、学生干部position、西部身份west、论文数量paper、奖学金money 进行学生信息的录入，并通过func()函数计算某个学生的奖学金money 利用sort函 ...

奖学金 原题链接：http://oj.haizeix.com/problem/375 某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。 期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。 输入： 共 n + 1 行。 第 1 行为一个正整数 n（6 ≤ n ≤ 300），表示该校参加评选的学生人数。 第 2 到 n + 1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100 之间。第 j 行的 3 个数字依次表示学号为 j−1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 n − 1（恰好是输入数据的行号减 1）。 输出： 共 5 行，每行是两个用空格隔开的正整数，依次表示前 5 名学生的学号和总分。 样例： 123456789880 89 8988 98 7890 67 8087 66 9178 89 9188 99 7767 89 6478 89 98 123458 2652 2646 2641 2585 258 思路： 构造student自定义类型，包含学生学号num、语文成绩chinese、数学成绩math、英语成绩english、总分all 进行学生信息的录入，并计算学生的总成绩 利用sort函数对student自定义类型按照给定的排序方式进行排序后进行输出 12345678910111213141516171819202122232425262728293031323334353637#include<iostream>#include<algorithm>using namespace std;//1.构造student自定义类型，包含学生所有信息struct student{ int num, chinese, math, english, all;};student stu[305];bool cmp(const student &a, const student &b){ if(a.all == b.all) ...

吃瓜群众 原题链接：http://oj.haizeix.com/problem/386 某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。 现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。 现在对于每组想吃瓜的群众，需要在 M 堆瓜中查找对应数量的一堆瓜，并输出那堆瓜的编号，若找不到对应数量的一堆，则输出 0。 输入： 输入共 3 行。 第一行两个整数 M,N。 第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同） 第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同） 输出： 对于每个 Yi 输出一行一个整数为对应数量的瓜的编号，若没有对应数量的瓜，则输出 0。 样例： 1235 31 3 26 7 1526 99 3 123302 1.参考解答思路1：暴力查找，每一组群众都对瓜堆进行遍历，时间复杂度为O(n^2)必超时 思路2： 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt 进行瓜堆信息的录入 利用sort函数对node自定义类型按照瓜的数量num进行排序 二分查找在瓜堆中查找，如果找到输出瓜堆数量num，否则输出0 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include<iostream>#include<algorithm>#include<cstring>using namespace std;//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cntstruct node { int num, cnt;};node wm[100005];bool cmp(const node &a, const node &b){ return a.cnt < b.cnt;}int main(){ int n, m; //2.进行瓜堆信息的录入 scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i)& ...

吃瓜群总升级版 原题链接：http://oj.haizeix.com/problem/387 某地总共有 M 堆瓜，第 i 堆瓜的数量为 Xi。 现有 N 组群众现在想要吃瓜，第 i 组群众想要吃的瓜的数量为 Yi。 现在对于每组想吃瓜的群众，需要在 M堆瓜中查找大于等于需要数量的第一堆瓜，并输出那堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。 输入： 输入共 3 行。 第一行两个整数 M,N。 第二行 M 个整数分别表示 X1,X2……XM。（保证各不相同） 第三行 N 个整数分别表示 Y1,Y2……YN。（保证各不相同） 输出： 对于每个 Yi 输出一行一个整数为大于等于需要数量的第一堆瓜的编号，若所有瓜堆的数量均小于需要数量，则输出 0。 样例： 1235 51 3 26 7 1527 10 3 4 2 1234505242 1.思路分析二分查找特殊情况的探讨01： 二分查找特殊情况的探讨10： 2.参考解答 构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cnt 进行瓜堆信息的录入 若所有瓜堆的数量均小于需要数量输出0，否则输出大于等于需要数量的第一堆瓜的编号 方法1：建立一个最大虚拟瓜堆并将瓜堆数量置为0，当正常瓜堆中没有瓜堆满足条件时输出虚拟瓜堆数量 方法2：用最大的瓜堆的瓜数量判断，如果最大瓜堆数量大于需求则有答案进行二分，否则直接输出0 利用sort函数对node自定义类型按照瓜的数量num进行排序 利用二分查找在瓜堆中查找，如果找到输出瓜堆数量num 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<algorithm>#include<cstdio>using namespace std;//1.构造node自定义类型，包含瓜堆编号num、瓜堆瓜的数量cntstruct node { int num, cnt;};node wm[100005];bool cmp(const node &a, const node &b){ return a.cn ...