Tian Ji -- The Horse Racing（贪心）

科技前沿 • 2025-03-14 09:13 • 阅读 36

大家好，我是讯享网，很高兴认识大家。

Tian Ji – The Horse Racing

题意：
田忌和齐王都有三匹不同类型的赛马，即下等马，中等马和上等马。规则是有三轮比赛，每一匹马只能在一轮中使用。单轮胜者从失败者那里获得两百银元。
因为齐王是齐国最有权势的人，齐王有很好的马，在每类赛马中他的马都比田忌的马好。因此，每次都是齐王赢田忌六百银元。
田忌为此很不高兴，直到他遇见了孙膑，孙膑是中国历史上最有名的军事家之一。由于孙膑使用一个小窍门，使得田忌赢了齐王两百银元。
这是一个相当简单的一个小窍门。田忌用下等马对齐王的上等马，他肯定会输掉这一轮。但随后他的中等马击败齐王的下等马，而他的上等马击败齐王的中等马。您如何评价田忌赛马？
如果田忌生活在现代，他一定会嘲笑他自己。更有甚者，现在他坐着参加ACM竞赛，他可能会发现，赛马的问题可以简单地被视为一个二分图最大匹配问题。在一边画上田忌的马，另一边画上齐王的马。当田忌的一匹马能击败齐王的一匹马，就在这两匹马之间画一条边，表示要建立这一对马的关系（如图）。因此，赢得尽可能多轮的的问题就是找到这个图的最大匹配。如果出现平局，问题就变得很复杂，就要给所有可能的边分配权重0，1或-1，并找到一个最大加权完善的匹配… …
然而，赛马的问题是二分图匹配的一个非常特殊的情况，马匹的速度决定这幅图 - 速度快的顶点击败速度慢的顶点。在这种情况下，加权二分匹配算法是处理这个问题的非常先进的工具。
在这个问题中，请您编写一个程序来解决匹配问题的这个特殊情况。

讯享网

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #define ll long long const int inf=0x3f3f3f3f; using namespace std; //田忌 int t[2000]; //齐王  int q[2000]; bool cmp(int a,int b) { 
    return a>b; } int main() { 
    int n; while(cin>>n,n) { 
    int use; for(int i=1;i<=n;i++) { 
    scanf("%d",&use); t[i]=use; } sort(t+1,t+1+n,cmp); for(int i=1;i<=n;i++) { 
    scanf("%d",&use); q[i]=use; } sort(q+1,q+1+n,cmp); int win=0; int tl=1,tr=n; int ql=1,qr=n; while(tl<=tr) { 
    if(t[tl]>q[ql]) { 
    win++; tl++; ql++; }else if(t[tr]>q[qr]){ 
    win++; tr--; qr--; }else if(t[tr]<q[ql]){ 
    win--; tr--; ql++; }else{ 
    //现在田忌最慢的对齐王现在最快的  tr--; ql++; } } cout<<200*win<<endl; } return 0; }

讯享网

Tian Ji -- The Horse Racing（贪心）

Tian Ji – The Horse Racing

相关推荐