kkbtrainingI

报数 原题链接：https://oj.haizeix.com/problem/382 N 个人围成一圈，编号分别为 1,2,3……N 第一个人从 1 报数，按照编号顺序依次报数， 报 M 的人会离开队伍，然后下一个人会继续从 1 开始报数，直到剩下一人，剩下的人的编号是多少？ 输入： 共一行两个数 N 和 M 输出： 输出一个数表示最后一人的编号。 样例： 17 3 14 代码1234567891011121314151617181920212223#include<iostream>#include<queue>using namespace std;queue<int> que;int main() { //队列模拟约瑟夫环 int n, m; cin >> n >> m; for(int i = 1; i <= n; ++i) que.push(i); int now = 1;//更新报1的位置 while(que.size() != 1){ if (now != m) { que.push(que.front()); now++; } else { now = 1; } que.pop(); } cout << que.front() << endl; return 0;}

海港 原题链接：https://oj.haizeix.com/problem/385 小李是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。 小李对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i 艘到达的船，他记录了这艘船到达的时间 ti (单位：秒)，船上的乘 客数 ki，以及每名乘客的国籍 xi,1, xi,2,…, xi,k。 小李统计了 n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 小时( 24 小时= 86400 秒）内所有乘船到达的乘客来自多少个不同的国家。 形式化地讲，你需要计算 n 条信息。对于输出的第 i 条信息，你需要统计满足 ti − 86400 < tp ≤ ti 的船只 p，在所有的 xp,j 中，总共有多少个不同的数。 输入： 第一行输入一个正整数 n，表示小李统计了 n 艘船的信息。 接下来 n 行，每行描述一艘船的信息：前两个整数 ti 和 ki 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 ki 个整数 xi,j 表示船上乘客的国籍。 保证输入的 ti 是递增的，单位是秒；表示从小李第一次上班开始计时，这艘船在第 ti 秒到达海港。 输出： 输出 n 行，第 i 行输出一个整数表示第 i 艘船到达后的统计信息。 样例： 12345//样例输入131 4 4 1 2 22 2 2 310 1 3 1234//样例输出1344 第一艘船在第 1 秒到达海港，最近 24 小时到达的船是第一艘船，共有 4 个乘客， 分别是来自国家 4,1,2,2，共来自 3 个不同的国家 第二艘船在第 2 秒到达海港，最近 24 小时到达的船是第一艘船和第二艘船，共有 4+2=6 个乘客，分别是来自国家 4,1,2,2,2,3，共来自 4 个不同的国家 第三艘船在第 10 秒到达海港，最近 24 小时到达的船是第一艘船、第二艘船和第 三艘船，共有 4+2+1=7 个乘客，分别是来自国家 4,1,2,2,2,3,3，共来自 4 个不同的国家 123456//样例输入241 4 1 2 2 33 2 2 386401 2 3 486402 1 5 12345//样例输出23334 第一艘船在第 1 秒到达海港 ...

桐桐的新闻系统 原题链接：https://oj.haizeix.com/problem/573 桐桐为期末的计算机作业设计了一套新闻系统，他把这套新闻系统称为 Argus。使用这套系统的用户可以向这套系统注册，然后这套系统就会以用户要求发送新闻的时间间隔向用户发送一次新闻。 向 Argus 注册的指令具有这样的格式：Register Qnum Period Qnum （0 < Qnum ≤ 30000） 是用户的 ID，Period（0 < Period ≤ 3000）是间隔。注册后 Period 秒，结果会第一次到达。 所有的用户都有不同的 Qnum。 桐桐测试了一段时间后，想知道系统前 K 次给谁发送新闻了。如果同一时间发送多个新闻，以 Qnum 的升序排列。 输入： 第一部分是注册指令，每条一行。指令数不超过 1000。此部分以 “ # ” 结束。 第二部分仅一行一个整数 K，K ≤ 10000。 输出： 输出前 K 个新闻发送到的用户的 Qnum，每行一个。 样例： 1234Register 2004 200Register 2005 300#5 1234520042005200420042005 代码思路：每次取时间最小的进行输出，同为时间最小时再按照ID进行排序，故应该使用优先队列进行处理。 1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>#include<queue>#include<string>using namespace std;struct node { int id; int offset;//获得新闻的时间 int next;//下一次获得新闻的时间（排序依据） bool operator<(const node &t) const {//重载小于号 实现大于号的功能(自定义优先队列的排序规则) if (this->next == t.next) return this->id > t.id; return this->next > t.next; }};priority_ ...

STL基本使用 STL六大组件： 容器 适配器 空间分配器：malloc 迭代器：高级指针 算法库：sort 仿函数：一个类重载一个括号 1.string类 string常用方法 find(what, start) substr(start, length) insert(start, what) replace(start, length, what) size()\length() 注意：find()返回值为第一个目标出现的下标值，若没有找到将返回string::npos(-1) 123456789101112131415161718192021222324252627#include <iostream>#include <string>using namespace std;int main(){ string str = "ABCDEF"; //1.输出字符串长度 cout << str.size() << endl; //2.查找字符串DE的位置 cout << str.find("DE") << endl; //3.输出没有查找到的结果 cout << (int)str.find("DE", 5) << endl; //4.字符串截取 cout << str.substr(3, 2) << endl; //5.字符串插入 str.insert(1, "abc"); cout << str << endl; //6.字符串替换 str.replace(2, 5, "000"); cout << str << endl; //7.一次性读入一行包含空格的字符串 string str1; getline(cin, str1); cout << str1 << endl; return 0;} ...

伐木 原题链接：http://oj.haizeix.com/problem/82 又到了伐木的季节，亚布力林业局引进了一台新的伐木设备： 这种设备能设定一个高度值（整数），并将所有树木大于此高度的部分锯下来。 例如，有四棵树的高度分别为20M、17M、15M、10M，把设备的高度设定为 15M，那么设备运行过后树的高度变为15M、15M、15M、10M（从第一棵树锯下 5M，从第二棵树锯下 2M，总共锯下 7M）。 现在林业局需要至少锯下长度为M米的木头，因为国家推行的环保政策，林业局不能锯下过多的木材。 需要将伐木设备的高度设定为多少才能使得获得的木材至少为 M 米？ 换句话说，如果再将高度升高一米，将得不到 M 米的木材，如果将高度减少一米，将不能通过环保政策。 输入： 第一行两个整数 N 和 M，N 表示树木的数量，M 表示需要木材的长度。（1 ≤ N ≤ 1000000 , 1 ≤ M ≤ 2000000000） 第二行 N 个整数表示每棵树的高度（N ≤ 1000000000）。所有数据必有解。 输出： 一个整数，表示伐木的最高高度。 样例： 124 920 17 15 10 114 1.思路 根据设定伐木设备的设定长度num[i]，利用fun()函数进行计算，能求出其能够获得的伐木量 根据当前能够获取的伐木量s与题目给定真实需要的伐木量m进行比较，从而调整左右指针 当左右指针逼近到一定范围时，表示最佳答案已经找到 2.代码实现1234567891011121314151617181920212223242526272829303132333435363738#include<iostream>using namespace std;long long n, m, num[1000005], rawr;long long func(long long x) { long long t = 0; for (int i = 0; i < n; ++i) { if (num[i] > x) { t += num[i] - x; } } return t;}long long bs() { ...

数列分段 原题链接：http://oj.haizeix.com/problem/391 对于给定的一个长度为 N 的正整数数列 Ai ，现要将其分成 M（M ≤ N）段，并要求每段连续、且每段和的最大值最小。 关于最大值最小： 例如一数列 4 2 4 5 1 要分成 3 段， 将其如下分段：[4 2] [4 5] [1]：第1段和为 6、第 2 段和为 9、第 3 段和为 1，和最大值为 9。 将其如下分段：[4] [2 4] [5 1]：第1段和为 4、第 2 段和为 6、第 3 段和为 6，和最大值为 6。 并且无论如何分段，最大值不会小于 6。 所以可以得到，要将数列 4 2 4 5 1 分成 3 段，每段和的最大值最小为 6。 输入： 第一行两个整数 N , M。（1 ≤ M ≤ N ≤ 100,000） 接下来 N 行，每行一个数，表示 Ai 。（1 ≤ Ai ≤ 100,000,000） 输出： 一个正整数，即每段和最大值最小为多少。 样例： 1234565 342451 16 1.思路 2.代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>using namespace std;long long n, m, num[100005], rawl, rawr;long long func(long long x) { long long t = 0, now = 0; for (int i = 0; i < n; ++i) { if (now + num[i] > x) { t++; now = num[i]; } else if (now + num[i] == x) { t++; now = 0; } else { now += num[i]; } } if (now != ...

跳石头 原题链接：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 ...