田忌賽馬
原來做過 但當(dāng)時(shí)思路很混亂 今天看到一個(gè)思路清晰的貪心 記錄一下
把雙方的馬從大到小排序 然后從前往后比較 老田贏了呢 就繼續(xù)往下比 老田比不過呢 就拉老田最慢的馬跟這個(gè)比 這里好理解
還有比平的情況 比平了還是從后面找一匹馬
找的時(shí)候 要是老田后面的馬可以贏對應(yīng)位置的馬 就接著往前比 然后找到的那匹就跟前面這匹馬比
核心代碼：
??? for(i=0;i<n;i++)
??? ??? {
??? ??? ??? if(t[head]>k[i])
??? ??? ??? {
??? ??? ??? ??? head++;
??? ??? ??? ??? ans+=200;
??? ??? ??? }
??? ??? ??? else if(t[head]<k[i])
??? ??? ??? {
??? ??? ??? ??? tailt--;
??? ??? ??? ??? ans-=200;
??? ??? ??? }
??? ??? ??? else if(t[head]==k[i])
??? ??? ??? {
??? ??? ??? ??? for(j=tailt,m=tailk;j>=head;j--,m--)
??? ??? ??? ??? {
??? ??? ??? ??? ??? if(t[j]>k[m])
??? ??? ??? ??? ??? {
??? ??? ??? ??? ??? ??? ans+=200;
??? ??? ??? ??? ??? ??? tailt--;
??? ??? ??? ??? ??? ??? tailk--;
??? ??? ??? ??? ??? }
??? ??? ??? ??? ??? else
??? ??? ??? ??? ??? ?{
??? ??? ??? ??? ??? ???? ? if(t[j]<k[i]) ans-=200;
??? ??? ??? ??? ??? ??? ? tailt=--j;
??? ??? ??? ??? ??? ??? ? tailk=m;
??? ??? ??? ??? ??? ??? ? break;??? ??? ??? ??
??? ??? ??? ??? ??? ?}
??? ??? ??? ??? }
??? ??? ??? }
??? ??? ??? if(head>tailt) break;
??? ??? }