欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2017年湖南省第十三届大学生计算机程序设计竞赛-D Tian Ji's Horse Race Again

程序员文章站 2022-03-26 14:13:21
...

2017年湖南省第十三届大学生计算机程序设计竞赛-D Tian Ji's Horse Race Again

地址:http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2000

思路:贪心。对于King的马a[n]和Tian的马b[n],交换的k匹马,肯定是取a[n]的最大值和b[n]的最小值交换,那么对于a[],b[]的比较排列是固定的,因此主要怎么求赢得次数,由于a,b都是由小到大排序的,因此可以先求出对于b[i]至少要交换多少匹马才能够使得b[i]赢,这样就可以把所有情况都先预处理好。

Code :

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

const int MAX_N=100005;
int n,Q;
int a[MAX_N],b[MAX_N];
int ans[MAX_N];

int main()
{
	while(~scanf("%d%d",&n,&Q)){
		for(int i=n-1;i>=0;--i)
			scanf("%d",&a[i]);
		for(int i=0;i<n;++i)
			scanf("%d",&b[i]);
		map<int,int> imap;
		for(int i=n-1,k=0;i>=0;--i)
		{
			while(k<n&&a[k]<b[i]){
				++k;
			}
			//对于b[i]至少要向右移多少个才能赢(不把右移的交换的情况下,即a[]不变) 
			int t=max(0,n-k-i);
			++imap[t];
			ans[i]=0;
		}
		int m=0,sum=0;
		for(auto c:imap)
		{
			sum+=c.second;
			//由于右移后的b[i]会到a[]去,因此只需要(c.first+1)/2就能够赢 
			m=(c.first+1)/2; 
			ans[m]=sum;
		}
		for(int i=1;i<=n;++i)
			if(!ans[i])	ans[i]=ans[i-1];
		while(Q--){
			scanf("%d",&sum);
			int res=n;
			if(sum<=m)	res=min(res,ans[sum]);
			printf("%d\n",res);
		}
	}
	
	return 0;
}

 

相关标签: 算法