程序员进阶之算法练习（四十六）
正文
题目1. Ichihime and Triangle
题目链接 题目大意： 输入4个整数? , ?, ?, ?, 并且 ?≤?≤?≤?； 现在需要找三个整数?, ?, ?，满足： ?≤?≤?. ?≤?≤?. ?≤?≤?. 并且?, ?, ?能构成一个三角形。
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行，四个整数? , ?, ?, ? (1≤?≤?≤?≤?≤10^9）
输出： 每个样例一行，三个s整数?, ?, ?；
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
样例解释 3 4 5
样例解释5 5 5
题目解析： 三角形要满足两边之和大于第三边，由题目意思我们知道x≤y≤z； 所以只要满足，x+y≥z即可； 所以令y=z，那么x随便取值即可。
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
题目链接 题目大意： 小明在打游戏，遇到了一条恶龙； 恶龙血量为x，小明可以释放两个技能： 技能1：使龙的血量变为x/2+10，x/2为向下取整； 技能2：使龙的血量减10； 当龙的血量小于等于零时，小明会赢得胜利；
小明最多可以释放n个技能1和m个技能2，现在想知道，小明是否能否打败恶龙；
输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行，整数? , ?, ? (1≤?≤10^5, 0≤?,?≤30)
输出： 每个样例一行，如果小明可以打败恶龙，输出YES；如果无法打败，则输出NO；
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
题目解析： 题目只考虑是否能打败，而不是最优解，可以直接将技能1释放完，只要技能1不会使恶龙血量增加； 然后再全部放完技能2，看最终血量是否小于等于0即可；
思考?： 贪心！
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
题目链接 题目大意： 有n个城市，用n-1条道路相连，并且保证任意两个城市之间都可以通过道路相连； 作为女王，小明需要选出k个城市作为工业城市，剩下的n-k个城市作为旅游城市。 城市1是首都，现在要召开工业会议，每个工业城市都会派出一个使者到城市1参加会议，使者会沿着道路按照最短的路径直接到达城市1，使者的快乐值等于沿途经过的旅游城市的数量。
小明想知道，如何选择工业城市，使得所有使者的快乐值总和最大？ （城市1可以是工业城市，也可以旅游城市） 输入： 第一行，整数 ? and ? (2≤?≤2⋅105, 1≤?<?) 接下来n-1行，每行两个整数 ? and ? ，表示城市u和城市v之间有一条道路 (1≤?,?≤?)
输出： 一个整数，表示所有使者的快乐值总和的最大值；
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
样例解释
题目解析： 一开始是用贪心的思路：先dfs遍历，记录每个点的深度和子节点的数量； 按照深度，从大到小排序，再按子节点的大小，从小到大排序； 然后，从深度最大的开始，填充节点；相同深度，优先填充子节点少的； 最后再遍历一遍，得到结果。 复杂度NlogN。
提交之后，喜提一个Wrong Answer。
重新思考：正确的做法是评估，每一个点的价值和代价，上面只考虑了价值，忽略了代价的问题。
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
题目链接 题目大意： 小明去商场购物，有若干个商品排成一行。 小明有n张优惠券，每张优惠券可以覆盖id范围是(l[i], r[i])的商品，包括第l[i]、r[i]个商品; 现在小明想从中选出k张优惠券，并且让这k张优惠券共同覆盖的商品尽可能多； 输出最多的商品数，还有选中的k张购物券。
输入数据 第一行两个整数，n and k (1 ≤ k ≤ n ≤ 3·1e5) 接下来n行，每行两个整数 l[i] and r[i] ( - 1e9 ≤ l[i] ≤ r[i] ≤ 1e9)
输出数据 第一行是最多覆盖的商品数； 第二行是k个整数，表示选中的k张购物券；
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 样例解释：没有共同覆盖的区间，任选两张即可。
题目解析： 容易知道优惠券的选择是没有先后顺序，可以对其进行排序。 先保证左区间从小到大，再考虑右区间从小到大。
对于购物券i覆盖的区间(l[i], r[i])，如果之前某个购物券（我们用j来表示），其覆盖区间的r[j] < l[i]; (j < i) 那么就有l[i] > r[j] >= l[j]; 即是购物券i的覆盖区间是在购物券j覆盖区间的右边； 并且对于购物券i+1覆盖区间，因为有l[i+1] >= l[i], 那么购物券 i+1的覆盖区间必然也是在购物券j的覆盖区间右边；
由此，我们可以维护一个优先队列：里面有若干个值，r最小的在前面，如果r相同则让大的在前面； 由于前面我们已经按照左区间从小到大排序，那么对于第i张优惠券，l[i]就是最大的left，再拿优先队列里面的top.r，就是最小右区间； l[i]和top.r形成的区间，就是优先队列里面的所有区间的公共覆盖区间，再判断下优先队列里面的区间是否大于k。
注意题目还要求输出k个优惠券，如果求解过程去记住这个值，很容易超时； 可以只记录最长的公共覆盖区间ans，输出答案的时候通过遍历所有优惠券，如果该优惠券的覆盖区间超过输出ans，则直接输出。
#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;
}总结
题目1是简单思维，三角形的基本性质； 题目2是典型的贪心题目，代码非常简单； 题目3是贪心类似的思路，可以用代价和价值来简化思考； 题目4要先对数据做预处理，是典型的区间覆盖问题。
腾讯云开发者
