正文
题目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
题目解析：
三角形要满足两边之和大于第三边，由题目意思我们知道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要先对数据做预处理，是典型的区间覆盖问题。
