题目描述
blablabla
样例
blablabla
算法1
总体思路:最差的马换最好的马, 再去比较最优值
1.s1 > s2 s1 vs s2
2 .s1 < s2 s1 vs f2
3. s1 = s2
3.1 f1 > f2 f1 vs f2
3.2 f1 < f2 s1 vs f2
3.3 f1 = f2 重点分析
左边 s1 vs f2 右边 s1 vs s2
从右边分析开始
前提 f1 == f2
设 f1 > x > s1
if (f2 > x) x vs s2 , f2 vs s1 or s1 vs s2 , f2 vs x 最好的情况 return 0 有解在左边
if (f2 < x) 不存在
if( f2 == x) 平局 return 0 最优解在左边 右边无解
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
const int N = 1010;
int n;
int a[N], b[N];
using namespace std;
int judge(int x, int y){
if(a[x] > b[y]) return 1;
if(a[x] < b[y]) return -1;
return 0;
}
int main(){
while(cin >> n , n){
for(int i = 0; i< n ;i++) cin >> a[i];
for(int i= 0; i< n; i++) cin>> b[i];
sort(a, a+n, greater<int>());
sort(b, b+n, greater<int>());
int f1 = 0, f2 = 0, s1 = n-1, s2 = n -1;
int res =0;
while(f1 <= s1){
if(judge(s1, s2) > 0) res++, s1--,s2--;
else if(judge(s1, s2) < 0) res+= judge(s1, f2), s1--, f2++;
else{
if(judge(f1, f2) > 0) res++, f1++, f2++;
else {
res += judge(s1, f2), s1--, f2++;
}
}
}
cout << res*200 << endl;
}
return 0;
}