Codeforces-429-2-C Leha and Function

本文主要是介绍Codeforces-429-2-C Leha and Function，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出两个串，第一个串称为A，第二个串称为B，两个串的长度相等，求的最大和， F(n, k)表示从1-n，你取出k的数字的子集， F(n, k)就等于你取出的k的数字中的最小值，而题目的要求就是让你重新给A排序，使得这个和值最大。

思路：我们每次从n个数字中取出k个数字时，最优的策略就是取n的前k个数字，这样肯定是最优的，那么给A重新排序的时候，我们可以这样想从n个数字中取出的数字越少和式肯定最大，所以此时我们只需要使得A串中的大的数对应B串中小的数，这样肯定是最大的

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=200050;
struct Dig
{int x;int idx;} d1[MAXN],d2[MAXN];
bool cmp1(Dig d1,Dig d2)
{return d1.x>d2.x;
}
bool cmp2(Dig d1,Dig d2)
{return d1.x<d2.x;
}
bool cmp3(Dig d1,Dig d2)
{return d1.idx<d2.idx;
}
int main()
{int n;scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&d1[i].x);d1[i].idx=i;}sort(d1,d1+n,cmp1);for(int i=0; i<n; i++){scanf("%d",&d2[i].x);d2[i].idx=i;}sort(d2,d2+n,cmp2);for(int i=0; i<n; i++){d1[i].idx=d2[i].idx;}sort(d1,d1+n,cmp3);for(int i=0; i<n; i++){printf("%d%c",d1[i].x,i==n-1?'\n':' ');}printf("\n");return 0;
}

这篇关于Codeforces-429-2-C Leha and Function的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---