UOJ#386. 【UNR #3】鸽子固定器(链表)

题意

题目链接

为了固定S**p*鸽鸽,whx和zzt来到鸽具商店选购鸽子固定器。 鸽具商店有 nn 个不同大小的固定器,现在可以选择至多 mm 个来固定S**p*鸽鸽。每个固定器有大小 sisi 和牢固程度 vivi。 如果他们选购的固定器大小不一或是不牢固,固定S**p*鸽鸽的时候肯定会很头疼,所以定义选择的物品总牢固程度和的 dvdv 次方减大小极差的 dsds 次方为这个方案的价值,求不同选购方案中,价值的最大值。

Sol

非常好的一道猜结论

如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

考虑到$M$很小,对于长度$\leqslant M$的部分直接暴力枚举

那长度$ > M$的呢?很显然,我们需要暴力里面$v$值较大的点

因此我们用一个链表维护处所有的数,然后从小到大枚举$v$值,同时枚举一下能覆盖到它的区间来更新答案

#include<cstdio>
#include<algorithm>
#include<queue>
#define Pair pair<int, int> 
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long
 #define int long long  
using namespace std;
const int MAXN = 2 * 1e5 + 10, B = 25000;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, ds, dv;
int l[MAXN], r[MAXN];
LL Get(LL x, int opt) {
    if(opt == 1) return x;
    else return x * x;
}
struct Node {
    int s, v;
    bool operator < (const Node &rhs) const {
        return s == rhs.s ? v < rhs.v : s < rhs.s;
    }
}a[MAXN];
main() {
    priority_queue<Pair> q;
    N = read(); M = read(); ds = read(); dv = read();
    for(int i = 1; i <= N; i++) {
        a[i].s = read(), a[i].v = read(); // 澶у皬 / 鐗㈠浐绋嬪害
        
    }
    sort(a + 1, a + N + 1);
    for(int i = 1; i <= N; i++) {
        q.push(MP(-a[i].v, i));
    }
    int ans = 0;
    for(int i = 1; i <= N; i++) {
        int sum = 0;
        for(int j = i; j <= i + M - 1 && j <= N; j++) {
            sum += a[j].v;
            ans = max(ans, Get(sum, dv) - Get(a[j].s - a[i].s, ds));
        }
    }
  // printf("%d\n", ans);
    for(int i = 1; i <= N; i++) r[i] = i + 1, l[i] = i - 1;
    while(!q.empty()) {
     //   printf("%d\n", q.top().fi);
        int pos = q.top().se; q.pop();
        int sum = a[pos].v, x = pos, y = pos;
        for(int j = 1; j < M; j++) {
            if(l[x]) x = l[x], sum += a[x].v;
            else if(r[y] <= N) y = r[y], sum += a[y].v;
        }
        while(x != r[pos] && y <= N) {
            ans = max(ans, Get(sum, dv) - Get(a[y].s - a[x].s, ds));
            sum -= a[x].v;
            x = r[x]; y = r[y];
            sum += a[y].v;
        }
        r[l[pos]] = r[pos];
        l[r[pos]] = l[pos];
    }
    printf("%lld", ans);
    
    return 0;
}
/*
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P3376 【模板】网络最大流

题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式 输入格式: 第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个...

30980
来自专栏杨建荣的学习笔记

使用贪心算法解决集合覆盖问题

有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。

14220
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述...

34160
来自专栏落影的专栏

程序员进阶之算法练习(十八)

前言 最近在接触新知识,也是选择2017年的方向。 其他文集更新会放缓,没有学习就没有心得,肚中无墨就无从下笔。 但是算法练习还是挺好玩的,欢迎关注algo...

35450
来自专栏mathor

第四届蓝桥杯决赛B组C/C++——空白格式化

12730
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

37960
来自专栏数据结构与算法

2488 绿豆蛙的归宿

2488 绿豆蛙的归宿 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 黄金 Gold 题目描述 Description   随着...

1.2K70
来自专栏聊聊技术

原 初学数模-MATLAB Quick S

46690
来自专栏数值分析与有限元编程

Fortran知识 | 还在使用reshape函数?

计算机内存是一维的,在存储多维数组时,有些语言按行优先原则,有些语言按列优先原则。Fortran语言就属于按列优先原则。 Fortran语言用reshape函数...

36670
来自专栏机器学习入门

POJ 刷题系列:1083. Moving Tables

POJ 刷题系列:1083. Moving Tables 传送门:POJ 1083. Moving Tables 题意: 一条走廊,两栏房间。搬运工每次从房价...

227100

扫码关注云+社区

领取腾讯云代金券