c++ 田忌赛马（史上最全）上海月赛乙组T3

原题连接: 上海市计算机学会竞赛平台 | YACS

---

一，思路

先对田忌和齐王的马的速度的数组进行一次从小到大的排序。

我们先比较田忌最快的马和齐王最快的马的速度。

一.若田忌获胜，就让这两匹马比赛。

二,若田忌最快的马跟齐王最快的马的速度相等，则比较他们最慢的马的速度。

1：田忌最慢的马比齐王最慢的马的速度快，则让它们比赛。

2：田忌最慢的马比齐王最慢的马的速度慢或者相等，则让田忌最慢的马和齐王最快的马比赛。

三,否则,用田忌最慢的马和齐王最快的马比赛。

---

二，WA + TLE祭

代码:

#include 
using namespace std;
long long n,qi[500005],ta[500005],fen,tn;
int main()
{
  scanf("%lld",&n);
  tn = n;
  for(int i = 1; i <= n; i++) scanf("%lld",&ta[i]);
  for(int i = 1; i <= n; i++) scanf("%lld",&qi[i]);
  sort(ta + 1,ta + 1 + n);
  sort(qi + 1,qi + 1 + n);
  for(int i = 1; i <= tn; i++) 
  {
    if(ta[n] > qi[n])
    {
      fen++;
      n--;
    }
    else if(ta[n] == qi[n])
    {
      if(ta[1] > qi[1])
      {
        fen++;
        for(int j = 2; j <= n; j++) ta[j - 1] = ta[j],qi[j - 1] = qi[j];
        n--;
      }
      else
      {
        fen--;
        for(int j = 2; j <= n; j++) ta[j - 1] = ta[j];
        n--;
      }
    }
    else
    {
      fen--;
      for(int j = 2; j <= n; j++) ta[j - 1] = ta[j];
      n--;
    }
  }
 printf("%lld",fen);
  return 0;
}

WA是因为在让田忌最慢的马和齐王最快的马比赛时忘了特判田忌赢,平局的情况

TLE是因为在比完一场比赛后为了不用一样的马重复比用了O(n)时间复杂度的删除操作

总共时间复杂度:O(n^2)

---

三,AC祭

因为我们的贪心策略只会动田忌和齐王最慢/快的马,

所以可以用qi_max来存储齐王最快马的下标,qi_min来存储齐王最慢马的下标,

ta_max来存储田忌最快马的下标,

ta_min来存储田忌最慢马的下标,

如果齐王的最快马比完赛了那么就qi_max--,

如果齐王的最慢马比完赛了那么就qi_min++,

如果田忌的最快马比完赛了那么就ta_max--,

如果田忌的最慢马比完赛了那么就ta_min++。

总共时间复杂度:O(n)

代码:

#include 
using namespace std;
long long n,qi[500005],ta[500005],fen,tn,ta_max,ta_min,qi_max,qi_min;
int main()
{
  scanf("%lld",&n);
  tn = n;
  for(int i = 1; i <= n; i++) scanf("%lld",&ta[i]);
  for(int i = 1; i <= n; i++) scanf("%lld",&qi[i]);
  sort(ta + 1,ta + 1 + n);
  sort(qi + 1,qi + 1 + n);
  ta_max = n,qi_max = n,ta_min = 1,qi_min = 1;
  while(n--)
  {
    if(ta[ta_max] > qi[qi_max])
    {
      ta_max--;
      qi_max--;
      fen++;
    }
    else if(ta[ta_max] == qi[qi_max])
    {
      if(ta[ta_min] > qi[qi_min])
      {
        ta_min++;
        qi_min++;
        fen++;
      }
      else
      {
        if(ta[ta_min] > qi[qi_max])
        {
          fen++;
          ta_min++;
          qi_max--;
        }
        else if(ta[ta_min] == qi[qi_max])
        {
          ta_min++;
          qi_max--;
        }
        else
        {
          fen--;
          ta_min++;
          qi_max--;
        }
      }
    }
    else
    {
      fen--;
      ta_min++;
      qi_max--;
    }
  }
  printf("%lld",fen);
  return 0;
}