[UOJ386]鸽子固定器

佚名 6年前 (2019-04-12) 随笔 830人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

堆+贪心
题意就是给你\(n\)个物品,让你最多选\(m\)个
每个物品有两个属性\(a_i,b_i\)
最大化\((\sum_{a_i})^{dv}+(max(b_i)-min(b_i))^{ds}\)
首先后面的那个东西看着不是很舒服
但是按照\(b\)为关键字排个序就可以消除\(b\)的影响了
那么我们只考虑\(a\)即可
以后我们可以发现答案所选择的物品一定是一个区间内最大的\(k\)个物品
所以我们可以固定一个右端点
然后不断向左扫去找前\(k\)大的值
这个东西可以用一个小根堆来实现
一旦右端点被弹出就结束寻找
这个复杂度是\(O(n^2)\)
可以在找最大值时用\(ST\)表+二分做到\(O(nlognlogm)\)
这个复杂度应该就可以卡着过了
当然我们可以对于每个位置处理出ta前面离ta最近的比ta大的值的位置
这样就省去了\(ST\)表+二分
复杂度变成了\(O(nlogn)\)
但是由于两个\(log\)直接跑过去了我就懒得写一个\(log\)的了

代码

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define LL long long
const int M = 200005 ;
const int N = 20 ;
using namespace std ;

inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ;  }
    return x*w ;
} 

int n , m , ds , dv ;
int lg[M] , sz[M] , val[M] , st[M][N] ;
LL ans , sum ;
struct Node { int sz , val ; } p[M] ;
struct Pion { int idx , val ; } ;
inline bool operator < (Pion a , Pion b) {
    return a.val > b.val ;
}
inline bool operator < (Node a , Node b) {
    return a.sz < b.sz ;
}
priority_queue < Pion > q ;

inline int query(int l , int r) {
    int j = lg[r - l + 1] ;
    return max( st[l][j] , st[r - (1 << j) + 1][j] ) ;
}
inline LL dc(LL sum , int x) {
    if(x == 1) return sum ;
    return 1LL * sum * sum ;
}

inline int Getpos(int rp) {
    int l = 1 , r = rp , ret = -1 , mid ;
    while(l <= r) {
        mid = (l + r) >> 1 ;
        if(query(rp - mid + 1 , rp) > q.top().val) ret = rp - mid + 1 , r = mid - 1 ;
        else l = mid + 1 ;
    }
    return ret ;
}
int main() {
    n = read() ; m = read() ; ds = read() ; dv = read() ;
    for(int i = 2 ; i <= n ; i ++) lg[i] = lg[i >> 1] + 1 ;
    for(int i = 1 ; i <= n ; i ++) p[i].sz = read() , p[i].val = read() ;
    sort(p + 1 , p + n + 1) ;
    for(int i = 1 ; i <= n ; i ++) {
        sz[i] = p[i].sz , val[i] = p[i].val ;
        st[i][0] = val[i] ;
    }
    for(int j = 1 ; j <= lg[n] ; j ++)
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
            st[i][j] = max( st[i][j - 1] , st[i + (1 << (j - 1))][j - 1] ) ;
    for(int i = 1 , pos ; i <= n ; i ++) {
        sum = 0 ;
        while(!q.empty()) q.pop() ;
        for(int j = i ; j >= i - m + 1 && j >= 1  ; j --) {
            q.push((Pion) { j , val[j] }) ;
            sum += val[j] ;
            ans = max( ans , dc(sum , dv) - dc(sz[i] - sz[j] , ds) ) ;
        }
        pos = i - m + 1 ; if(pos <= 1) continue ;
        bool exist = true ;
        while(exist) {
            if(q.top().idx == i) break ;
            pos = Getpos(pos - 1) ; if(pos < 0) break ;
            sum += val[pos] - q.top().val ;
            ans = max( ans , dc(sum , dv) - dc(sz[i] - sz[pos] , ds) ) ;
            q.pop() ; q.push((Pion) { pos , val[pos] }) ;
        }
    }
    printf("%lld\n",ans) ;
    return 0 ;
}