題意：
? ? ? 田忌和齊王賽馬，兩個(gè)人每人n匹馬，每個(gè)馬都有自己的速度，贏一場得到200分，輸一場失去200分，平則不得分，問田忌可能得到的最高得分是多少？


思路:
? ? ? 又是一個(gè)比較經(jīng)典的貪心小題目，這個(gè)題目很容易想到，就是我們先排序，然后我們這樣想，如果我們是田忌，對方是齊王，首先我們可以拿最快的那個(gè)馬和他最快的那個(gè)馬比一下，如果能贏，那么直接比賽，得到一分，這個(gè)不用質(zhì)疑，因?yàn)橛米约旱淖顝?qiáng)去得分的同時(shí)還削弱的對方的最強(qiáng)，這個(gè)果斷是最優(yōu)的，然后如果比不過呢？比不過就有可能面臨著這一局要輸?shù)墓?jié)奏，反正也是輸，我們就找一個(gè)我們最小的去和他最大的比，去浪費(fèi)他的最大的，這樣輸?shù)挠袃r(jià)值，但是這是后要注意一點(diǎn)，就是如果我們最小的比他的最小的大，那么我們還不如用我們最小的和他的最小的比一次，先贏200分，前面的那個(gè)打不過先放一下，在處理晚處理都一樣，現(xiàn)在能贏一次是一次，那么整理后就是這樣：先用最想的和他最強(qiáng)的比，如果能打贏就打，否則就看看我們最弱的能不能打得過他的最弱的，如果能贏就直接比，否則就拿最弱的去換他最強(qiáng)的，輸?shù)挠袃r(jià)值點(diǎn)，還有就是有一個(gè)小地方要注意，如果我們打算用最弱的換最強(qiáng)的了，發(fā)現(xiàn)最弱的和他最強(qiáng)的一樣，那么這時(shí)候我們是不輸錢的，其實(shí)這個(gè)時(shí)候應(yīng)該是直接可以break了吧，我沒想錯(cuò)的話這個(gè)時(shí)候雙方剩下的所有馬的速度都是一樣的。




#include<stdio.h>
#include<algorithm>


#define N 1000 + 10


using namespace std;


bool camp(int a ,int b)
{
? ?return a > b;
}


int num1[N] ,num2[N];


int main ()
{
? ?int i ,n ,l1 ,l2 ,r1 ,r2, Ans;
? ?while(~scanf("%d" ,&n) && n)
? ?{
? ? ? for(i = 1 ;i <= n ;i ++)?
? ? ? ? scanf("%d" ,&num1[i]);
? ? ? for(i = 1 ;i <= n ;i ++)?
? ? ? ? scanf("%d" ,&num2[i]);
? ? ? sort(num1 + 1 ,num1 + n + 1 ,camp);
? ? ? sort(num2 + 1 ,num2 + n + 1 ,camp);
? ? ? l1 = l2 = 1 ,r1 = r2 = n;
? ? ? Ans = 0;
? ? ? while(n--)
? ? ? {
? ? ? ? ?if(num1[l1] > num2[l2])
? ? ? ? ?{
? ? ? ? ? ? l1 ++ ,l2 ++;
? ? ? ? ? ? Ans ++;
? ? ? ? ?}
? ? ? ? ?else if(num1[r1] > num2[r2])
? ? ? ? ?{
? ? ? ? ? ? r1 -- ,r2 --;
? ? ? ? ? ? Ans ++;
? ? ? ? ?}
? ? ? ? ?else
? ? ? ? ?{
? ? ? ? ? ??
? ? ? ? ? ? if(num1[r1] < num2[l2])?
? ? ? ? ? ? ? Ans --;
? ? ? ? ? ? r1 -- ,l2 ++;
? ? ? ? ? ??
? ? ? ? ?}
? ? ? }
? ? ? printf("%d\n" ,Ans * 200);
? ?}
? ?return 0;
}
? ? ??
? ? ??

總結(jié)

以上是生活随笔為你收集整理的LA3266田忌赛马的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。