Strength(HDU6563+2018年吉林站+双指针瞎搞)
2024-08-30 04:47:15
题目链接
题意
你有\(n\)只怪,每只怪的伤害为\(a_i\),对手有\(m\)只怪,每只怪的伤害为\(b_i\),对手的怪有普通状态和防守状态(普通状态:如果你用攻击力为\(a_i(a_i\geq b_j)\)的怪去攻击对手第\(j\)只怪将会给对手造成\(a_i-b_j\)的伤害;防守状态则不会造成\(a_i-b_j\)的伤害),每只怪只能使用一次,怪一旦死亡就会消失。
用攻击力为\(x\)的怪去打攻击力为\(y(x\leq y\),\(x\geq y\)的情况上面说了\()\)的怪会有以下两种情况:
- \(x<y\):对手不受到任何伤害,自己的怪死亡;
- \(x=y\):对手不受到任何伤害,双方的怪死亡;
如果对手所有的怪都死亡了,那么你就可以直接攻击对手且伤害为你的怪的伤害值。
问你你能给对手造成的最大伤害值是多少。
思路
本题分两种情况进行考虑:
- 全部的怪都去打对手普通状态的怪,注意这种情况下不能直接攻击对手。
- 将防守状态和普通状态的怪都打死,然后用剩余的怪去打对手。
我们知道用剩余怪中伤害值大的去打对手剩余怪中伤害值大的是最优解(如果用伤害值大的去打其他怪的话,到后面可能会导致有怪打不死对手伤害值高的怪),因此用两个双指针瞎搞就可以了。
代码实现如下
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://Code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
const double eps = 1e-8;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int t, n, m;
vector<int> vec1, vec2;
int a[maxn], vis1[maxn], vis2[maxn];
struct node {
int val, pos;
bool operator < (const node& x) const {
return val < x.val;
}
}pp[maxn];
int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
scanf("%d", &t);
int icase = 0;
while(t--) {
scanf("%d%d", &n, &m);
vec1.clear(), vec2.clear();
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
vis1[i] = 0;
}
sort(a + 1, a + n + 1);
for(int i = 1; i <= m; ++i) {
scanf("%d", &pp[i].val);
vis2[i] = 0;
}
int num = 0, flag = 1;
for(int i = 1; i <= m; ++i) {
scanf("%d", &pp[i].pos);
if(pp[i].pos) ++num, flag = 0;
}
sort(pp + 1, pp + m + 1);
if(n > num) {
for(int i = 1, j = 1; i <= n; ++i) {
while(!pp[j].pos) ++j;
if(j > m) break;
if(a[i] >= pp[j].val) {
--num;
vis1[i] = vis2[j] = 1;
++j;
}
}
}
for(int i = 1; i <= n; ++i) {
if(vis1[i]) continue;
vec1.emplace_back(a[i]);
}
for(int i = 1; i <= m; ++i) {
if(vis2[i] || pp[i].pos) continue;
vec2.emplace_back(pp[i].val);
}
LL ans1 = 0, ans2 = 0;
for(int i = vec1.size() - 1, j = vec2.size() - 1; i >= 0; --i) {
while(j >= 0 && vec1[i] < vec2[j]) --j;
if(j < 0 && num == 0) {
ans1 += vec1[i];
continue;
} else if(j < 0) continue;
ans1 += vec1[i] - vec2[j];
--j;
}
for(int i = n, j = m; i >= 0; --i) {
while(j > 0 && (pp[j].pos || pp[j].val > a[i])) --j;
if(j <= 0 && flag) {
ans2 += a[i];
continue;
} else if(j <= 0) continue;
ans2 += a[i] - pp[j].val;
--j;
}
printf("Case %d: %lld\n", ++icase, max(ans1, ans2));
}
return 0;
}
最新文章
- 用FlexGrid做开发,轻松处理百万级表格数据
- 如何在Eclipse中查看JDK以及JAVA框架的源码(转载)
- 关于eclipse入门开发c/c++文章推荐
- LeetCode:Unique Binary Search Trees I II
- Python第九章模块和包(2)
- TabControl控件
- c# DirectoryInfo类 详解
- 解决OpenCV Error:Insufficient memory(Failed to allocate 1244164 bytes) in unknown function
- 3、MapReduce
- sulime-text 3 安装以及使用
- 多校联合练习赛1 Problem1005 Deque LIS+LDS 再加一系列优化
- meta viewport标签的使用说明(手机浏览缩放控制)
- BitMap - leetcode [位运算]
- 基于vip和twemproxy代理实现redis集群的无感知弹性扩容
- C#封装程序集属性方法注释说明
- jquery.form.js ajax提交上传文件
- [转]通过设置nginx的client_max_body_size解决nginx+php上传大文件的问题
- DVWA安装——一个菜鸟的入门教程
- Windows 之 防火墙
- Java集合 之Map(HashMap、Hashtable 、TreeMap、WeakHashMap )理解(new)