题解:

首先预处理出$l_i$表示第$i$个数左侧比第$i$个数大的个数,$r_i$右侧同理.

首先脑补出我们应该将序列排成先单调不降,后单调不增的形式.

我们从大到小将数插入序列,考虑插入某个数,比这个数大的已经全部插入完毕了,由于排成那种形式,我们只能将这个数放在当前序列的头或尾.

若放在开头,则带来$l_i$的逆序对;否则带来$r_i$的逆序对.

显然每个数之间都是独立的,我们直接贪心就行了.

时间复杂度$O(nlogn)$.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

#define N 300010
int n,_n,a[N],b[N];

inline int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
inline int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

int A[N],l[N],r[N];
inline int ask(int x){
	int re=0;
	for(;x;x-=x&-x)
		re+=A[x];
	return re;
}
inline void upd(int x){
	for(;x<=_n;x+=x&-x)
		++A[x];
}
int main(){
	n=getint();
	int i,j;
	for(i=1;i<=n;++i)
		a[i]=b[i]=getint();
	sort(b+1,b+n+1);
	_n=unique(b+1,b+n+1)-b-1;
	for(i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+_n+1,a[i])-b;
	for(i=1;i<=n;++i){
		l[i]=i-1-ask(a[i]);
		upd(a[i]);
	}
	memset(A,0,sizeof A);
	for(i=n;i>=1;--i){
		r[i]=n-i-ask(a[i]);
		upd(a[i]);
	}
	long long ans=0;
	for(i=1;i<=n;++i)
		ans+=min(l[i],r[i]);
	cout<<ans<<endl;
	return 0;
}

思路:

假设在能逃出相同多数目的小矮人的情况下,我们更愿意让逃生能力更强的小矮人留到最后.

逃生能力就是指\(a_i+b_i\),也即在下面垫的总高度确定时更容易达到更高的高度.

这样我们就有了一个贪心选择顺序,我们设\(f[i]\)表示逃生了\(i\)个小矮人时下面垫的总高度的最大值,并依据这个判定能否再逃出一人即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 2010
struct Case{int a,b;bool operator<(const Case&B)const{return a+b<B.a+B.b;}}S[N];
 
int f[N];
int main(){
    int n,m;scanf("%d",&n);register int i,j;for(i=1;i<=n;++i)scanf("%d%d",&S[i].a,&S[i].b);
    sort(S+1,S+n+1);
    scanf("%d",&m);
    memset(f,-1,sizeof f);for(f[0]=0,i=1;i<=n;++i)f[0]+=S[i].a;
    int ans=0;
    for(i=1;i<=n;++i){
        for(j=ans;j>=0;--j){
            if(f[j]+S[i].b>=m)f[j+1]=max(f[j+1],f[j]-S[i].a);
             
        }if(f[ans+1]>=0)++ans;
    }
    printf("%d\n",ans);
    return 0;
}

思路:

我们维护以每一个节点为根的子树内部有多少个没有确定权值的点,另外,我们利用一个数组维护每个权值已经给了哪个节点.

我们从小到大遍历每个权值,若这个权值当前并没有确定给哪个节点,则将其压入栈中;否则我们在对应节点的子树中进行一系列确定操作:

我们维护栈中有多少个权值,以及有多少个自由权值.(这个是什么一会再说)

若未确定的节点数正好等于当前的自由权值数与栈中的权值总数,显而易见这些权值都应该分配给这棵子树.但是只有只有一个儿子的情况才能确定这个权值.所以我们不断在链上去找即可.这个过程可能确定了一些权值,随后我们将栈清空,并令自由权值的数目为0.因为他们只能被拘束在这颗子树内,而不能去别的地方.

若不然,我们将自由权值及栈中的权值分配给这棵子树所需要的数目,剩下的全部变成自由权值.

我们发现栈中的权值和自由权值很像,但是为什么不都搞成自由权值,而是非要维护一个栈呢?

这个问题显而易见:自由权值都是可以互相交换的(等价的),而栈中的元素显然不是!

于是\(O(n)\)水.