TOJ-1188-田忌赛马(贪心）

题意：

田忌和齐王赛马，胜一场可得200金，负一场损失200金，平局无得失。

给出马的数量和田忌每匹马的速度，齐王每匹马的速度，求出田忌最多可以赢得多少金。

最大最小解问题，贪心

思路：

按照速度对田忌和齐王的马进行降序排序，

如果当前田忌马的最高速度大于齐王马，赢

田忌马最高速度小于齐王马，用田忌最低马速度对齐王当前马，输

如果当前两者速度相等，分两种情况

       田忌最低速度大于齐王最低速度，赢

       田忌最低速度小于等于齐王最低速度，平局或输

代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iomanip>
#include<algorithm>

using namespace std;
const int maxn=1100;
typedef long long ll;

int n;
int a[maxn],b[maxn];
int cmp(int a,int b)
{
  return a>b;
}
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];

    int t,ans=0;
    sort(a,a+n,cmp);
    sort(b,b+n,cmp);

    int l1=0,l2=0,r1=n-1,r2=n-1;
    while(l1<=r1)
    {
      if(a[l1]>b[l2])
      {
        ans+=200;
        l1++;
        l2++;
      }
      else if(a[l1]<b[l2]){
        ans-=200;
        r1--;
        l2++;
      }
      else if(a[l1]==b[l2]&&a[r1]>b[r2]){
        ans+=200;
        r1--;
        r2--;
      }
      else if(a[l1]==b[l2]&&a[r1]<=b[r2]){
        if(a[r1]<b[l2]) ans-=200;
        r1--;
        l2++;
      }
    }
    cout<<ans<<endl;
  }
  system("pause");
  return 0;
}