【UOJ#386】【UNR#3】鸽子固定器（贪心）

题面

UOJ

题解

一个不难想到的暴力做法是把东西按照\(s\)排序，这样子我们枚举极大值和极小值，那么我们选择的一定是这一段之间\(v\)最大的那\(m\)个东西。

考虑优化这个过程，我们枚举右端点，左端点向左移动，每次插入一个元素，用堆来维护选择的过程。这样子复杂度可以做到\(O(n^2logn)\)。

考虑继续优化这个过程，首先如果右端点一旦被弹出堆这个过程就可以终止了，这个很显然。

通过这个过程，我们也可以明白如果选择的个数不超过\(m\)个则必定是一段连续的区间。

接下来一定要选择恰好\(m\)个，如果区间内没有被选满，不难知道没有被选的一定是较小的值。

那么拿一个链表来维护剩下的元素，每次把最小值删掉，这样子每次选择的区间就是连续的了。然后我们在删的时候统计强制包含最小值的最大区间。

于是综上复杂度是\(O(nm)\)。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 200200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Node{int s,v;}p[MAX];

bool operator<(Node a,Node b){return a.s<b.s;}

bool cmp(int a,int b){return p[a].v<p[b].v;}

int n,m,ds,dv,id[MAX],lt[MAX],nt[MAX];

ll ans,s[MAX];

ll CalcS(ll x){return ds==1?x:x*x;}

ll CalcV(ll x){return dv==1?x:x*x;}

int St[MAX],tot;

int main()

{

	n=read();m=read();ds=read();dv=read();

	for(int i=1;i<=n;++i)p[i].s=read(),p[i].v=read();

	sort(&p[1],&p[n+1]);

	for(int i=1;i<=n;++i)s[i]=s[i-1]+p[i].v;

	for(int l=1;l<m;++l)

		for(int i=1;i+l-1<=n;++i)

			ans=max(ans,CalcV(s[i+l-1]-s[i-1])-CalcS(p[i+l-1].s-p[i].s));

	for(int i=1;i<n;++i)nt[i]=i+1,lt[i+1]=i;

	for(int i=1;i<=n;++i)id[i]=i;

	sort(&id[1],&id[n+1],cmp);

	for(int i=1;i<=n;++i)

	{

		int u=id[i];tot=0;

		for(int j=1,p=lt[u];j<m&&p;++j,p=lt[p])St[++tot]=p;

		reverse(&St[1],&St[tot+1]);St[++tot]=u;

		for(int j=1,p=nt[u];j<m&&p;++j,p=nt[p])St[++tot]=p;

		for(int j=1;j<=tot;++j)s[j]=s[j-1]+p[St[j]].v;

		for(int j=1;j+m-1<=tot;++j)

			ans=max(ans,CalcV(s[j+m-1]-s[j-1])-CalcS(p[St[j+m-1]].s-p[St[j]].s));

		nt[lt[u]]=nt[u];lt[nt[u]]=lt[u];

	}

	printf("%lld\n",ans);

	return 0;

}