19-11-06-&

你&我处于这里……在一起？

$$\text{%%%Wearry}$$

ZJ：

一遇到Wearry的思维题就得×得够呛。

考试心态炸裂，码上三个暴力然后就不知道该干啥了。

现在就想敲自己。

不要放弃一点点分！

Miemeng

00:00:22

00:00:23

摁 end 键就能找到我啦！

UPD:

××晚上梦见自己省三是不是要死了？？？

TJ：

先改了下T2，觉得再不写博客就AFO了非常妙然后先写个。

T2：

考试根本没想法，（$12$的数据范围意思就是$O(N!) \sim O(1)$都……）

一点提示都没有（主要是自己太菜啥都没想出来）

首先应该转换题意。

如果你真的想把中间的变成最大的，为什么不把小的放在左右两边呢？

因为并没有规定最大值的位置。

这样的转换（感性理解）是正确的。

所以……

$10\%$算法

每次找区间最小值，然后比较它距离左右的距离，然后暴力向短的方向左右移。

不要问我为什么$10\%$，此算法并没有考虑同等大小的数的优先级。

$30\%$算法

考虑区间里如果有两个最小值怎么办？

从贪心的角度看，应该将距离左/右侧最小的进行移动。

我们证明这种操作的正确性。

现在有左右两个相同小的值，它们之间的值全部比它们大所以就不具体画出了。

那么我们就又有许多情况。

右向左($B>A+k'$)

右向右($B<A+k'$)

左向左

$(A<B+k)$

先让左向左会更优

没有顺序的影响。

两种操作顺序不影响答案

左向右

$(A>B+k)$

有可能？？

先让右向右答案更优

那么我们解简单不等式：

当$A<B$时我们先将左向左移动更优。

当$A>B$时我们先将右向右移动更优。

得到$30$分

#include <iostream>

#include <cstring>

#include <climits>

#include <cstdio>

// #include "debug.h"

#define N 111111

using namespace std;

int len;

int arr[N],ans=0;

void dfs(int l,int r){

	if(l==r) return ;

	int minn=INT_MAX,id;

	for(int i=l;i<=r;i++){

		if( minn > arr[i]){

			minn = arr[i];

			id   = i;

		}

		else if( minn == arr[i] && min(r-id,id-l) > min(r-i,i-l)){

			id = i;

		}

	}

	if(r-id > id-l){

		ans+=id-l;

		for(int i=id;i>=l+1;i--)

			arr[i]=arr[i-1];

		arr[l]=minn;

		dfs(l+1,r);

	}

	else{

		ans+=r-id;

		for(int i=id;i<=r-1;i++)

			arr[i]=arr[i+1];

		arr[r]=minn;

		dfs(l,r-1);

	}

}

int main(){

#ifndef LOCAL

	freopen("time.in" ,"r",stdin);

	freopen("time.out","w",stdout);

#endif

	ios_base::sync_with_stdio(false);

	cin>>len;

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

		cin>>arr[i];

	dfs(1,len);

	cout<<ans<<endl;

}

$100\%$算法

我们已经在上面解决了许多的前趋问题，于是我们发现每次移动的答案贡献只有它向前/后比它大的块数，比它小的和等于它的全都会提前换到指定位置导致它没办法和它换（人家先占好坑了）。

那么用个全职权值树状数组。

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 111111

using namespace std;

int len;

int arr[N];

int pre[N],aft[N];

int ans;

namespace szsz{

	int arr[N];

	const int size=100010;

	inline int lowbit(int x){

		return x&(-x);

	}

	void add(int pos,int v){

		while(pos<=size){

			arr[pos]+=v;

			pos+=lowbit(pos);

		}

	}

	int query(int pos){

		int res=0;

		while(pos){

			res+=arr[pos];

			pos-=lowbit(pos);

		}

		return res;

	}

	void clear(){

		memset(arr,0,sizeof arr);

	}

}

int main(){

#ifndef LOCAL

	freopen("time.in" ,"r",stdin);

	freopen("time.out","w",stdout);

#endif

	ios_base::sync_with_stdio(false);

	cin>>len;

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

		cin>>arr[i];

	for(int i=1;i<=len;i++){

		pre[i]=szsz::query(100000) - szsz::query(arr[i]);

		szsz::add(arr[i],1);

	}

	szsz::clear();

	for(int i=len;i>=1;i--){

		aft[i]=szsz::query(100000) - szsz::query(arr[i]);

		szsz::add(arr[i],1);

	}

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

		ans+=min(pre[i],aft[i]);

	cout<<ans<<endl;

}

巴特西

19-11-06-&

ZJ：

UPD:

TJ：

T2：

$10\%$算法

$30\%$算法

$100\%$算法

最新文章

热门文章