必威体育Betway必威体育官网
当前位置:首页 > IT技术

地中海气候

时间:2019-10-17 14:41:10来源:IT技术作者:seo实验室小编阅读:61次「手机版」
 

地中海气候

题意

有一个包含 N 个正整数的序列,序列元素不大于 N。紧接着,他们维护了一

个可重集合 S,包含序列中的前 P 个元素。Alice 先手,二人轮流进行下面的一

系列操作:

  1. 从集合 S 中拿走一个元素,加到玩家的总分上面;
  2. 将序列中的下一个数字(如果存在)添加到集合 S 中;

    假使二人都尽力使自己的总分最大,设游戏的结果为 Alice 的总分与 Bob 的

    总分之差,那么请你在给定序列和集合元素的情况下,输出游戏的结果

    N<=100000,Q<=2000

题解

为了简单,我们可以看做本来只有P-1个元素,然后是先插入,再取出

比较显然的性质是,每次都是取的multiset中最大那个元素

于是我们就直接上个multiset或者优先队列,成功得到再nlogn的时间内搞定每次询问

那么现在的问题是怎么优化

我们必须优化到O(n)内完成每次查询

必须发现的一点是,每次我们只会往这个multiset中插一个值,而且如果这个值大于了当前的最大值,就一定会被马上取走

那么也就是说,这个最大值一定是不增的

那么如果当前增加值是大于这个最大值,就一定给当前的人加上这么多分

那如果不是呢?我们会取出最大值,然后插入当前的这个值。

那么问题来了怎么实现呢?

二分链表?或者干脆直接上个二叉堆?似乎那个log怎么都砍不掉啊?

然而…考虑到所有数都小于等于n,我们可以直接用一个数组来维护出现次数…成功实现O(1)插入,然后更新最大值暴力更新即可,由于是单调不增的,可以证明是O(n)的

于是最后O(NQ)解决本题

记得开ll

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=100005;
int n,m;
int a[N],cnt[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        int p;
        scanf("%d",&p);
        int mx=0;
        for(int j=1;j<=p-1;j++){
            cnt[a[j]]++;
            mx=max(mx,a[j]);
        }
        ll ans=0;
        for(int j=1,k=1;j<=n;j++,k*=-1){
            if(p+j-1<=n){
                if(a[p+j-1]>mx)
                    ans+=k*a[p+j-1];
                else{
                    ans+=k*mx;
                    cnt[a[p+j-1]]++;
                    cnt[mx]--;
                    while(mx>0&&!cnt[mx])
                        mx--;
                }
            }
            else{
                ans+=k*mx;
                cnt[mx]--;
                while(mx>0&&!cnt[mx])
                    mx--;
            }
        }
        printf("%lld\n",ans);
    }
}

相关阅读

当当卖身记:证明只挣读书人钱成不了气候

当当还是被卖了。这个曾经号称&ldquo;中国的亚马逊&rdquo;、&ldquo;最大的中文网上书城&rdquo;,中国第一家完全基于线上业务、在美

艺术衍生品电商为何始终难成气候?

由于尚未出现独角兽平台出现,也不失为创业者们从各环节切入艺术衍生品市场大展拳脚的好时机。艺术家授权厂商使用其创作的艺术品进

艺术衍生品电商为何始终难成气候?

由于尚未出现独角兽平台出现,也不失为创业者们从各环节切入艺术衍生品市场大展拳脚的好时机。艺术家授权厂商使用其创作的艺术品进

分享到:

栏目导航

推荐阅读

热门阅读