# 程序员进阶之算法练习（四十六）

### 正文

#### 题目1. Ichihime and Triangle

Examples input 4 1 3 5 7 1 5 5 7 100000 200000 300000 400000 1 1 977539810 977539810

output 3 4 5 5 5 5 182690 214748 300999 1 977539810 977539810

```    int t;
cin >> t;
while (t--) {
int a[4];
for (int i = 0; i < 4; ++i) {
cin >> a[i];
}
cout << a[1] << " " << a[2] << " " << a[2] << endl;
}   ```

#### 题目2. Kana and Dragon Quest game

Examples input 7 100 3 4 189 3 4 64 2 3 63 2 3 30 27 7 10 9 1 69117 21 2 output YES NO NO YES YES YES YES

```    int t;
cin >> t;
while (t--) {
int x, n, m;
cin >>x >> n >> m;
while (n && (x / 2 + 10 < x)) {
--n;
x = x / 2  +10;
}
if (x <= m * 10) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}   ```

#### 题目3. Linova and Kingdom

Examples input 7 4 1 2 1 3 1 4 3 5 3 6 4 7 output 7

input 4 1 1 2 1 3 2 4 output 2

```vector<int> g[N];
int vis[N];

void dfsCount(int u, int dep) {
node[u].first = dep;
node[u].val = u;
vis[u] = 1;
for (int i = 0; i < g[u].size(); ++i) {
int v = g[u][i];
if (!vis[v]) {
dfsCount(v, dep + 1);
node[u].second += node[v].second + 1;
}
}
node[u].cost = dep - node[u].second;
}

int main(int argc, const char * argv[]) {
// insert code here...

int n, k;
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfsCount(1, 0);
sort(node + 1, node + n + 1);

lld sum = 0;
for (int i = 1; i <= k; ++i) {
sum = sum + node[i].cost;
}
cout << sum << endl;

return 0;
}```

#### 题目4. Fedor and coupons

Examples input 4 2 1 100 40 70 120 130 125 180 output 31 1 2 样例解释： 共同覆盖的区间是[40, 70]，总共有31种商品； input 3 2 1 12 15 20 25 30 output 0 1 2 样例解释：没有共同覆盖的区间，任选两张即可。

```#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long lld;
const int N = 301000, M = 3010100, inf = 0x7fffffff;
const lld llinf = 0x7fffffff7fffffffll;

struct Node {
int l, r, id;
bool operator < (const Node &tmp) const
{
if (r != tmp.r) return r > tmp.r; // 优先队列默认是大顶堆，但是我们希望r小的在前面
else return l < tmp.l; // 如果r相同，那么希望l大的在前面
};
Node(int first, int second, int id):l(first), r(second), id(id){};
Node(){};
}a[N];

bool cmp(Node x, Node y) {
if (x.l != y.l) {
return x.l < y.l;
}
else {
return x.r < y.r;
}
}

int main(int argc, const char * argv[]) {
// insert code here...
int k, n;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &a[i].l, &a[i].r);
a[i].id = i + 1;
}
sort(a, a + n, cmp);
priority_queue<Node> priQueue;
int ans = 0;
pair<int, int> seg;
for (int i = 0; i < n; ++i) {
// 优先队列里面有若干个值，r最小的在前面，假设是top.r，l最大的是l[i]，那么这些区间的公共区域是 l[i] 到 r
while (!priQueue.empty()) {
Node top = priQueue.top();
if (top.r < a[i].l) {
priQueue.pop();
continue;
}
else {
break;
}
}
while (priQueue.size() >= k) {
priQueue.pop();
}

if (priQueue.size() == k - 1) {
int topR;
if (priQueue.size() == 0) {
topR = a[i].r;
}
else {
topR = min(priQueue.top().r, a[i].r);
}
if (ans < topR - a[i].l + 1) {
ans = topR - a[i].l + 1;
seg = make_pair(a[i].l, topR);
}
}
priQueue.push(a[i]);
}

if (ans == 0) {
cout << 0 << endl;
for (int i = 0; i < k; ++i) {
printf("%d ", i + 1);
}
}
else {
cout << ans << endl;
for (int i = 0; i < n && k; ++i) {
if (a[i].l <= seg.first && a[i].r >= seg.second) {
printf("%d ", a[i].id);
--k;
}
}
cout << endl;
}

return 0;
}```

0 条评论

• ### 程序员进阶之算法练习（十六）

前言 正文6道题目来自leetcode––为求职为生的编程网站，目的是工作闲暇之时锤炼代码功底。 没有捷径，但手熟尔； 一步领先，步步领先。 正文 5. L...

• ### 程序员进阶之算法练习（四十四）

题目链接 题目大意： 给出整数x，求两个整数a和b，满足： ???(?,?)+???(?,?)=? . GCD是最大公约数； LCM是最小公约数；

• ### 程序员进阶之算法练习（十四）

前言 坚持做算法练习对开发的好处是抽象能力变强，拿到一个需求能很快对其进行抽象，然后再用学过的设计模式相关知识进行整理，最后用代码实现。 最大的好处在于：对...

• ### 程序员进阶之算法练习（二十六）

前言 金三银四，求职黄金月做算法面试题，热热身子。 正文 1.Chess For Three 题目链接 题目大意： 有三个人A,B,C玩剪刀石头布的游戏，但...

• ### 程序员进阶之算法练习（二十四）

前言 已经有三个月未更新算法文章，大厂工作环境是步步紧逼的，使得所有的人越来越忙碌。余下的学习时间，要用于技术预研、知识面开阔、底层原理理解等等，慢慢算法只能占...

• ### 程序员进阶之算法练习（四十二）

题目链接 题目大意： n个学生参加测试，一共有m道题，每道题的答案可能是(A, B, C, D , E)中的一个； m道题分别有?1,?2,…,??，共m...

• ### 程序员进阶之算法练习（四十七）

题目链接 题目大意： 给出一个整数1~n的排列。 接下来有m个询问，每个询问包括 l, r, x。 (l <= x <= r) [l, r]区间内的数字...

• ### 程序员进阶之算法练习（四十五）

每个路口的机动车道有三个方向，分别是左转、直行、右转，同时路口有一条人行道； 每行输入有四个数字l，s，r，p，分别表示左转、直行、右转、人行道的交通信号灯是...

• ### 程序员进阶之算法练习（四十一）

题目链接 题目大意： 有一个由数字0、1组成的字符串，长度为n； 现在需要将其切分成若干段，要求每一段0和1的数量是不相同的。 比如说1, 101, 0...