首页 > 代码库 > Codeforces 798D：Mike and distribution
Codeforces 798D：Mike and distribution
Codeforces 798D：Mike and distributio
题目链接：http://codeforces.com/problemset/problem/798/D
题目大意：给出两个大小为$n$的数列$A,B$，现要求从这两个数列相同位置取出$K（K \leqslant n/2+1）$个数，使得$2 \times subA>sumA$且$2 \times subB>sumB$.
想法题
我们需要从数列$A$和数列$B$中取出$K$个数，使得这$K$个数的和比剩下$n-K$个数的和大，显然$K=n/2+1$.
考虑一个大小为偶数$m$的数组，将数组分成$m/2$组，每两个数取较大数，则取出的数的和一定比剩下的数的和大.
讨论$n$为奇数的情况，将数组$A$降序排序，先取出最大的$A_x$和相对应的$B_y$。
剩下$m=n-1$（$m$为偶数）个数，按顺序两两分成一组，每两个数取对应数组$B$中较大数，保证了$subB>sumB-subB$，而由$A$数组的单调性，不难得出$subA>sumA-subA$.
同理可以证明$n$为偶数时算法的正确性.
复杂度为$O（nlgn）$.
代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 #define N 100005 4 using namespace std; 5 typedef long long ll; 6 int n,a[N],b[N],p[N]; 7 bool cmp(int x,int y){ 8 return a[x]>a[y]; 9 }10 int main(void){11 scanf("%d",&n);12 for(int i=0;i<n;++i)scanf("%d",&a[i]);13 for(int i=0;i<n;++i)scanf("%d",&b[i]);14 for(int i=0;i<n;++i)p[i]=i;15 sort(p,p+n,cmp);16 printf("%d\n",n/2+1);17 printf("%d",p[0]+1);18 for(int i=1;2*i<n;++i){19 int x=p[2*i-1],y=p[2*i];20 if(b[x]<b[y])printf(" %d",y+1);21 else printf(" %d",x+1);22 }23 if(n%2==0)printf(" %d",p[n-1]+1);24 }
Codeforces 798D：Mike and distribution
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。