AtCoder - ABC 160 - DE（贪心）D - Line++E - Red and Green Apples（贪心）

65 阅读 0 评论 43 点赞

我是靠谱客的博主激昂马里奥，最近开发中收集的这篇文章主要介绍AtCoder - ABC 160 - DE（贪心）D - Line++E - Red and Green Apples（贪心），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

D - Line++

题意：

有一个有 N 个点的无向图G，相邻两点间有一条边，在顶点 X, Y 之间加一条边，总共有 N 条边。对于k从 1 到 N，求出对于每个 k，图G中满足两点最短路径为 k 的整数对数。

数据范围：

3 ≤ N ≤ 2× $10^{3}$

1 ≤ X, Y ≤ N

X + 1 < Y

思路：

枚举起点和终点，按不加 x,y 的路径和加上 x,y 的路径，得出两种路径距离，取 Min，用数组下标记录距离，数组值记录该距离的路径数。

Code:

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#include<math.h>
using namespace std;
//#define x first
//#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
typedef pair<int, int>PII;
const int N = 200010, INF = 0x3f3f3f3f;
int ans[2010];
void solve()
{
int n, x, y;
int a, b, d;
cin >> n >> x >> y;
//输入点数；特殊点
for (int i = 1; i <= n; i++)
//枚举起点
for (int j = i + 1; j <= n; j++)
//枚举终点
{
a = j - i;
//a时不考虑特殊点的从i到j路径距离
接下来是考虑特殊点都在路径中(i -> x -> y -> j)
//if (x > i)
//如果特殊起点位于i的右侧
//	b = x - i;
//算上i->x的距离
//else
//如果在i的左侧
//	b = i - x;
//相当于从点i先向前走到点x，距离为i-x
//if (y > j)
//如果特殊终点位于j的右侧
//	b += y - j;
//算上j->y的距离
//else
//位于j的左侧
//	b += j - y;
//相当于从i->x后再x->y最后y->j，加的就是最后y->j的距离
//b += 1;
//这个1是x->y的距离1
b = (x > i ? x - i : i - x) + (y > j ? y - j : j - y) + 1;
//上面注释部分的简易写法
d = min(a, b);
//路径i->j的最短路径为d
ans[d]++;
//用数组累计最短路径为d的路径个数
}
for (int i = 1; i < n; i++)cout << ans[i] << endl;
//依次输出路径最短距离为1~n-1的路径个数
puts("");
}
signed main()
{
IOS;
int t = 1;
//int t;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}

E - Red and Green Apples（贪心）

题意：

有 A 个红苹果，B个绿苹果，C个白颜色苹果，每个苹果都有一个美味值 x 。吃白苹果可以当做红苹果或者绿苹果。现在需要吃 X 个红苹果，Y 个绿苹果使得所吃的苹果的美味值之和最大。

数据范围：

1 ≤ X ≤ A ≤ $10^{5}$

1 ≤ Y ≤ B ≤ $10^{5}$

1 ≤ C ≤ $10^{5}$

1 ≤ x ≤ $10^{9}$

思路：

因为无颜色的苹果可以代替红/绿苹果；将红,绿苹果美味值从大到小排序，将红苹果a的前x个数与绿苹果b的前y个数单拿出来，作为待选，放入未染色的c数组中，再对c数组从大到小排序，取前x+y个即可。
因为都放在C数组中，总共取x+y个苹果，这里面已经有x个红,y个绿了，既使是前x+y个中有未染色的苹果，它是可以染色的从而替换掉美味值更低的某颜色的苹果。

Code:

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#include<math.h>
using namespace std;
//#define x first
//#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
typedef pair<int, int>PII;
const int N = 200010, INF = 0x3f3f3f3f;
int x, y, aa, bb, cc;
int a[N], b[N], c[N];
void solve()
{
cin >> x >> y >> aa >> bb >> cc;
for (int i = 0; i < aa; i++)cin >> a[i];
for (int i = 0; i < bb; i++)cin >> b[i];
for (int i = 0; i < cc; i++)cin >> c[i];
//红，绿苹果按从大到小排序
sort(a, a + aa, greater<int>());
sort(b, b + bb, greater<int>());
//将红苹果前x个，绿苹果前y个加入c数组中
for (int i = 0; i < x; i++)c[cc++] = a[i];
for (int i = 0; i < y; i++)c[cc++] = b[i];
//对未染色的苹果从大到小排序
sort(c, c + cc, greater<int>());
int res = 0;
for (int i = 0; i < x + y; i++)res += c[i];
//取前x+y个苹果美味值
cout << res << endl;
}
signed main()
{
IOS;
int t = 1;
//int t;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
吐槽：看完题解后感觉这两题也不难，害，越打越菜><。总结下：

1.写D题时看到图和最短路径，脑子开始想的是最短路径算法模板啥的，根据时间复杂度发现不可，然后又想多一条边对是对于多的这一条边对哪些k有影响，举半天例子模拟分析也不对。┓(;´_｀)┏，没想到直接枚举起点终点，根据是否有特殊点取Min，数组记录输出。

2.写F题时脑子就轴着往背包问题那偏，想不出模型还死想。实际用贪心，害写题少太菜了没看不出。继续努力啊>-<。