「题解」:$Game$
2024-09-06 05:57:42
问题 B: $Game$
时间限制: 1 Sec 内存限制: 256 MB
题面
题面谢绝公开。
题解
对于最初加入的每一个元素开桶记录出现次数。
然后记录一个前p个元素最大值。
先由先手玩家取走一个最大值并判定最大值是否改变。
然后就可以先向集合中加入一个元素再由本轮取数的玩家取走最大的数字。
如果加入的元素大于最大值,由本轮取数的玩家直接取走。否则累加该数$sum$,取走一个最大值。
这样可以保证指针单调不升,减少指针移动次数。离散化可以进一步减少指针移动次数。
(然而我常数写丑了并不能A掉。多谢评测机放过在下。原封不动的代码多交几遍就A了)
#include<bits/stdc++.h>
#define rint register int
using namespace std;
inline void read(int &A)
{
A=;int B=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')B=-;ch=getchar();}
while(ch>=''&&ch<=''){A=(A<<)+(A<<)+ch-'';ch=getchar();}
A=A*B;
}
int n,k,a[],sum[],mx,lsh[];
long long ans1,ans2;
int main()
{
read(n),read(k);
for(rint i=;i<=n;++i)read(a[i]),lsh[i]=a[i];
sort(lsh+,lsh+n+);
rint cnt=unique(lsh+,lsh+n+)-lsh-;
for(rint i=;i<=n;++i)
a[i]=lower_bound(lsh+,lsh+cnt+,a[i])-lsh;
for(rint Round=,pi;Round<=k;++Round)
{
read(pi);ans1=ans2=;
for(rint i=;i<=pi;++i)
++sum[a[i]],mx=max(mx,a[i]);
ans1+=lsh[mx];--sum[mx];
while(!sum[mx]&&mx>)--mx;
for(rint i=;i<=n;++i)
{
if(i&)
{
if(pi<n)
{
++pi;
if(a[pi]>mx)ans1+=lsh[a[pi]];
else ans1+=lsh[mx],--sum[mx],++sum[a[pi]];
}
else ans1+=lsh[mx],--sum[mx];
}
else
{
if(pi<n)
{
++pi;
if(a[pi]>mx)ans2+=lsh[a[pi]];
else ans2+=lsh[mx],--sum[mx],++sum[a[pi]];
}
else ans2+=lsh[mx],--sum[mx];
}
if(i==n)break;
while(!sum[mx]&&mx>)--mx;
}
printf("%lld\n",ans1-ans2);
}
return ;
}
最新文章
- WdatePicker 使用
- Debian8修改启动默认运行级别
- A+B
- HDU-3790-最短路径
- ASP.NET 日志
- 在Linux系统安装VMware Tools
- 【.NET】使用HtmlAgilityPack抓取网页数据
- 关于PHP单双引号解析变量的问题
- iOS 11 &; iPhone X 适配资料集
- 调试和运行matlab代码(源程序)的技巧和教程
- socket实现FTP上传下载功能
- 一种快速构造和获取URL查询参数的方法:URLSearchParams
- redis 配置 架构 基础
- C++Primer笔记——文本查询程序(原创,未使用类)
- 51nod 1577 异或凑数
- selenium 定制启动 chrome 的选项
- PAT 1003 我要通过!(20)(代码+思路)
- 算法:堆排序(Heap Sort)
- C++ extern c 用法
- CentOS7添加开机启动服务/脚本(延用CentOS6方法)