PTA-8

1
```
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000;
struct node
{
    int a,b;
    double c;
}a[N+1];

int main()
{
   int n,m;
   cin>>n>>m;
   for(int i =0;i <n;i++)
   {
      cin>>a[i].a>>a[i].b;
      a[i].c = a[i].b/a[i].a ;
   }
   sort(a,a+n,[](node x,node y){
    return x.c > y.c;
   });
   double ans = 0;
   int s = 0;
   for(int i =0;i <n;i++)
   {
     if(s + a[i].a <= m)
     {
      ans += a[i].b;
      s += a[i].a;
     }
     else
     {
      ans += (m - s)*a[i].c;
      break;
     }
   }
    printf("%.2lf",ans);
    return 0;
}
```

2
```
#include <iostream>
#include <string>
#include <map>
using namespace std;
const int N = 1000;
struct node
{
    string start,end;
    int v;
};

map<string,node> a;

int main()
{
    string k;
    int v;
    cin>>k>>v;
    int n;
    cin>>n;
    for(int i =0;i <n;i++)
    {
        node n ;
        cin>>n.start>>n.end>>n.v;
        a[n.start] = n;
    }
    while(true)
    {
        if(a.find(k) != a.end())
        {
           v+=a[k].v;
           k = a[k].end;
        }
        else
        {
           break;
        }

}
    cout<<v<<endl;
  
    return 0;
}
```

3
```
#include <iostream>
#include <vector>
#include <algorithm>  // 排序函数sort的头文件
using namespace std;

// 计算田忌的最大得分，参数：田忌的马、齐王的马、马匹数量n
int maxScore(vector<int>& tian, vector<int>& qi, int n) {
    // 核心步骤1：对双方的马进行升序排序
    sort(tian.begin(), tian.end());
    sort(qi.begin(), qi.end());

int score = 0;  // 田忌最终得分
    // 双指针初始化：tl/tr是田忌的左右指针，ql/qr是齐王的左右指针
    int tl = 0, tr = n - 1;
    int ql = 0, qr = n - 1;

// 核心步骤2：贪心策略遍历，直到所有马比赛完毕
    while (tl <= tr) {
        if (tian[tl] > qi[ql]) {
            // 情况1：田忌最弱赢齐王最弱，得2分
            score += 2;
            tl++;
            ql++;
        } else if (tian[tl] < qi[ql]) {
            // 情况2：田忌最弱输齐王最强，得0分（止损）
            tl++;
            qr--;
        } else {
            // 情况3：田忌最弱 == 齐王最弱，比较最强马
            if (tian[tr] > qi[qr]) {
                // 子情况1：田忌最强赢齐王最强，得2分
                score += 2;
                tr--;
                qr--;
            } else {
                // 子情况2：田忌最强 ≤ 齐王最强，田忌最弱对齐王最强
                if (tian[tl] == qi[qr]) {
                    score += 1;  // 平局得1分
                }
                // 输则得0分，无需处理score
                tl++;
                qr--;
            }
        }
    }
    return score;
}

int main() {
    int n;
    cin>>n;
    vector<int> tian;
    vector<int> qi;
    int k;
    for(int i = 0;i < n;i ++)
    {
        cin>>k;
        tian.push_back(k);
    }
    for(int i = 0;i < n;i ++)
    {
        cin>>k;
        qi.push_back(k);
    }
    cout << maxScore(tian, qi, n) << endl;

return 0;
}
```