Java教程

题解 数数

本文主要是介绍题解 数数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

除了我基本都A了……就很丢人

考场上先猜了个结论：\(k=i\) 的情况是 \(k=i+1\) 的最优解删掉一个数
发现有这个结论就可以做了
那么我们可以设法维护每个点与其它点差的绝对值的和
每次取这个和最小的那个数删掉就可以了
现在的难点在于动态维护每个数与其它数的绝对值的差的和并支持区间取max
我只会 \(n^2\) 的

然而正解根本不用数据结构
有结论：先将原数组排序，每次分两种情况

  1. \(k\) 是偶数：取前 \(\frac{k}{2}\) 个和后 \(\frac{k}{2}\) 个一定更优
  2. \(k\) 是奇数：从左右已选个数最少的那边再选一个数

尝试证明：
当 \(k\) 为偶数时，考虑加入一个数的贡献
令大于它的数和为 \(sum_{max}\)， 个数为 \(cnt_{max}\)
则贡献为 \(sum_{max}-a[i]*cnt_{max} - a[i]*cnt_{min}-sum_{min}\)
因为 \(cnt_{max}=cnt_{min}=\frac{k}{2}\) ，所以 \(a[i]\) 消掉了
为了使后面仍保持性质我们从最边上选

当 \(k\) 为奇数时，两个 \(cnt\) 差为1
为了最大化贡献，我们从数少的那边再选一个
得证

Code: 
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
#define N 300010
#define ll long long
#define pb push_back
#define reg register int
//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n;
ll a[N];

namespace force{
	int ans, k;
	vector< vector<int> > sta;
	void dfs(int u, int pos, vector<int> v, int sum) {
		v.pb(a[pos]);
		for (auto it:v) sum+=abs(a[pos]-it);
		if (u==k) {
			if (ans<sum) ans=sum, sta.clear(), sta.pb(v);
			else if (ans==sum) sta.pb(v);
			return ;
		}
		for (int i=pos+1; i<=n; ++i) {
			dfs(u+1, i, v, sum);
		}
	}
	void solve() {
		for (int i=1; i<=n; ++i) {
			ans=0; sta.clear(); k=i;
			for (int j=1; j<=n; ++j) dfs(1, j, vector<int>(), 0);
			printf("%d\n", ans);
			for (auto it:sta) {for (auto i:it) printf("%d ", i); printf("\n");}
			cout<<endl;
		}
		exit(0);
	}
}

namespace task1{
	vector<int> v;
	int val[N], sum, sta[N], top;
	void solve() {
		for (int i=1; i<=n; ++i) v.pb(a[i]);
		for (int j=0; j<v.size(); ++j)
			for (int k=j+1; k<v.size(); ++k)
				sum+=abs(v[j]-v[k]);
		sta[++top]=sum;
		for (int i=2; i<=n; ++i) {
			for (int j=0; j<v.size(); ++j) {
				val[j]=0;
				for (int k=0; k<v.size(); ++k) val[j]+=abs(v[j]-v[k]);
			}
			ll minn=INF, mini;
			for (int j=0; j<v.size(); ++j) {
				if (val[j]<minn) minn=val[j], mini=j;
			}
			sum-=minn;
			sta[++top]=sum;
			v.erase(v.begin()+mini);
		}
		while (top) {
			printf("%d\n", sta[top--]);
		}
		exit(0);
	}
}

namespace task2{
	int top;
	ll val[N], sum, sta[N], lst=INF;
	bool del[N];
	void solve() {
		ll t;
		for (reg j=1; j<=n; ++j)
			for (reg k=j+1; k<=n; ++k) {
				t=llabs(a[j]-a[k]);
				sum+=t; val[j]+=t; val[k]+=t;
			}
		sta[++top]=sum;
		for (reg i=2; i<=n; ++i) {
			//cout<<"i: "<<i<<endl;
			ll minn=INF, mini;
			for (reg j=1; j<=n; ++j) if (!del[j]) {
				//cout<<"j: "<<val[j]<<endl;
				if (lst!=INF) val[j]-=llabs(a[j]-lst);
				if (val[j]<minn) minn=val[j], mini=j;
			}
			sum-=minn;
			sta[++top]=sum;
			del[mini]=1; lst=a[mini];
		}
		while (top) {
			printf("%lld\n", sta[top--]);
		}
		exit(0);
	}
}

namespace task3{
	int top;
	ll b, c, sta[N];
	void solve() {
		for (int i=1; i<=n; ++i)
			if (a[i]) ++c;
			else ++b;
		sta[++top]=b*c;
		for (int i=2; i<=n; ++i) {
			if ((b-1)*c > b*(c-1)) --b;
			else --c;
			sta[++top]=b*c;
		}
		while (top) {
			printf("%lld\n", sta[top--]);
		}
		exit(0);
	}
}

namespace task{
	ll sum[N], ans;
	void solve() {
		sort(a+1, a+n+1);
		for (int i=1; i<=n; ++i) sum[i]=sum[i-1]+a[i];
		int pos1=0, pos2=n;
		for (int i=1; i<=n; ++i) {
			if (pos1 == n-pos2) {
				ans += sum[n]-sum[pos2]-a[pos2]*(n-pos2);
				ans += a[pos2]*pos1-sum[pos1];
				--pos2;
			}
			else {
				ans += sum[n]-sum[pos2]-a[pos1+1]*(n-pos2);
				ans += a[pos1+1]*pos1-sum[pos1];
				++pos1;
			}
			printf("%lld\n", ans);
		}
		exit(0);
	}
}

signed main()
{
	bool all01=1;
	n=read();
	for (int i=1; i<=n; ++i) {
		a[i]=read();
		if (a[i]!=0 && a[i]!=1) all01=0;
	}
	//force::solve();
	//if (all01) task3::solve();
	//else task2::solve();
	task::solve();
	
	return 0;
}
这篇关于题解 数数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航