2017年湖南省第十三届大学生计算机程序设计竞赛-D Tian Ji's Horse Race Again
程序员文章站
2022-03-26 14:13:21
...
地址: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;
}
上一篇: hexo搭建