【C++贪心】P9228 原神|普及

admin 管理员组

文章数量: 1184232

本文涉及知识点

C++贪心

原神

题目背景

提示：题目背景与题目无关。

你说的对，但是《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。游戏发生在一个被称作「提瓦特」的幻想世界，在这里，被神选中的人将被授予「神之眼」，导引元素之力。你将扮演一位名为「旅行者」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘「原神」的真相。

因为你的素养很差，我现在每天玩原神都能赚 150 原石，每个月差不多 5000 原石的收入， 也就是现实生活中每个月 5000 美元的收入水平，换算过来最少也 30000 人民币，虽然我 只有 14 岁，但是已经超越了中国绝大多数人（包括你）的水平，这便是原神给我的骄傲的资本。

毫不夸张地说，《原神》是 miHoYo 迄今为止规模最为宏大，也是最具野心的一部作品。即便在经历了 8700 个小时的艰苦战斗后，游戏还有许多尚未发现的秘密，错过的武器与装备，以及从未使用过的法术和技能。

尽管游戏中的战斗体验和我们之前在烧机系列游戏所见到的没有多大差别，但游戏中各类精心设计的敌人以及 Boss 战已然将战斗抬高到了一个全新的水平。就和几年前的《塞尔达传说》一样，《原神》也是一款能够推动同类游戏向前发展的优秀作品。

题目描述

原神中有一个魔法师，她可以打出 $ n $ 次火元素攻击魔法和 $ m $ 次冰元素攻击魔法，每次攻击的伤害分别为 $ a_1,a_2,\cdots, a_n $ 和 $ b_1,b_2,\cdots, b_m $。

元素攻击之间存在如下反应规则：

• 每次元素攻击可以给没有元素附着的怪物附着相应的元素，初始时怪物没有元素附着；

• 如果用火元素攻击打到冰元素附着的怪物身上，那么本次伤害将 $ \times 2 $，并清空元素附着；

• 如果用冰元素攻击打到火元素附着的怪物身上，那么本次伤害将 $ +k $，并清空元素附着。

现在魔法师可以任意安排攻击顺序，也就是说，每次攻击过后，魔法师可以从自己没有使用过的魔法中任意挑选一种使用。她希望最大化总伤害，请问最大总伤害是多少。

输入格式

第一行三个整数 $ n,m,k $。

第二行 $ n $ 个整数 $ a_1,a_2,\cdots, a_n $。

第三行 $ m $ 个整数 $ b_1,b_2,\cdots, b_m $。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

6 7 3
1 1 4 5 1 4
1 9 1 9 8 1 0

样例输出 #1

67

样例 #2

样例输入 #2

5 3 5
1 4 2 8 5
7 1 4

样例输出 #2

50

样例 #3

样例输入 #3

1 1 0
2
3

样例输出 #3

7

样例 #4

样例输入 #4

见附件中的 samples/genshin4.in

样例输出 #4

见附件中的 samples/genshin4.ans

样例 #5

样例输入 #5

见附件中的 samples/genshin5.in

样例输出 #5

见附件中的 samples/genshin5.ans

提示

样例 1 解释

攻击采用 $a_1\rightarrow b_4\rightarrow a_2\rightarrow b_3\rightarrow a_5\rightarrow b_5\rightarrow b_7 \rightarrow b_1\rightarrow a_3 \rightarrow b_2\rightarrow a_4\rightarrow b_3 \rightarrow a_6 $，每次的实际伤害为 1 , 12 , 1 , 4 , 1 , 11 , 0 , 1 , 8 , 9 , 10 , 1 , 8 1,12,1,4,1,11,0,1,8,9,10,1,8 1,12,1,4,1,11,0,1,8,9,10,1,8，总伤害为 $ 67 $。

样例 2 解释

攻击采用 a 5 → b 1 → b 2 → a 4 → a 3 → b 3 → a 2 → a 1 a_5\rightarrow b_1\rightarrow b_2\rightarrow a_4\rightarrow a_3\rightarrow b_3\rightarrow a_2\rightarrow a_1 a5​→b1​→b2​→a4​→a3​→b3​→a2​→a1​，每次的实际伤害为 5 , 12 , 1 , 16 , 2 , 9 , 4 , 1 5,12,1,16,2,9,4,1 5,12,1,16,2,9,4,1，总伤害为 $50 $。

数据规模与约定

对于 100 % 100\% 100% 的数据，$1 \leq n,m \leq 10^6 ， ， ， 0 \leq a_i,b_i,k \leq 10^9 $。

贪心

总伤害=基础伤害+附加伤害
两种附加伤害，都需要一次火攻，一次冰攻。故最多有p=max(n,m)次附加伤害。
从a中选取p个最大数值，如果小于k取k。之和就是附加伤害。
如果火附加，先冰后火。如果冰附加，先火后冰。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret;
	T d ;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

class Solution {
public:
	long long MaxD(vector<int>& a, vector<int>& b, int k) {
		const int p = min(a.size(), b.size());
		sort(a.begin(), a.end(), greater<>());
		vector<int> c(p, k);
		for (int i = 0; (i < p) && (a[i] > k); i++) {
			c[i] = a[i];
		}
		long long ans = accumulate(a.begin(), a.end(), 0LL) + accumulate(b.begin(), b.end(), 0LL)
			+ accumulate(c.begin(), c.end(), 0LL);
		return ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n,m,k;	scanf("%d%d%d", &n,&m,&k);
	auto a = Read<int>(n);
	auto b = Read<int>(m);
	auto res = Solution().MaxD(a, b, k);
	cout << res << std::endl;
	return 0;
}

单元测试

	vector<int> a, b;
		TEST_METHOD(TestMethod11)
		{
			a = { 1, 1, 4, 5, 1 ,4 }, b = { 1 ,9, 1 ,9 ,8 ,1 ,0 };
			auto res = Solution().MaxD(a, b, 3);
			AssertEx(67LL, res);
		}
		TEST_METHOD(TestMethod12)
		{		
			a = { 1, 4, 2, 8 ,5 }, b = { 7 ,1 ,4 };
			auto res = Solution().MaxD(a, b, 5);
			AssertEx(50LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			a = { 2}, b = {3 };
			auto res = Solution().MaxD(a, b, 0);
			AssertEx(7LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			a = { (int)1e9 }, b = { (int)1e9 };
			auto res = Solution().MaxD(a, b, (int)1e9-1);
			AssertEx((long long)3e9, res);
		}
		TEST_METHOD(TestMethod15)
		{
			a = { (int)1e9 }, b = { (int)1e9 - 1 };
			auto res = Solution().MaxD(a, b, (int)1e9 );
			AssertEx((long long)3e9-1, res);
		}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文标签： 贪心