9.26 贪心专题

· · 算法·理论

贪心

T1 B3928 [GESP202312 四级] 田忌赛马（简单版）

没有思考的贪心，没有平局，且只需要求最大的获胜次数即可，所以可以直接排序，之后使用两个指针 i,j 代表枚举至第几匹马，如果能赢就立刻将 i+1,j+1 如果无法获胜就拿更高级的马继续比，直到没有马了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,ans(0);
int a[maxn],b[maxn];
int main(){
    cin>>n;
    for(int i(1);i<=n;i++){
        cin>>a[i];
    }
    for(int i(1);i<=n;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    int i(1),j(1);
    while(i<=n&&j<=n){
        if(b[j]<a[i]){
            i++; //如果可以就立刻赢
            j++;
            ans++;
        }else{
            i++; //拿更高级的马
        }
    }
    cout<<ans<<'\n';
    return 0;
}

T2 P1650 田忌赛马（加强版）

比T1难得多，需要考虑的变成了最大利益，赢一局200钱，输一局-200前，平局不加不扣

面对这种情况，一开始想的和上一题一样，赢的越多不就更优吗？其实只争赢的局数最大无法保证最优，比如赢一局，输两局和平三局明显是不一样的结果，平三局明显更优

所以对于这种情况我们的思路是：

  1. 比较最大值
  2. 如果田忌最大值小于齐王的，就比较最小值
  3. 如果最小值也比不过就去消耗齐王最大值

使用双端队列对思路进行模拟，使其比数组操作起来更简单

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
int n,ans(0);
int a[maxn],b[maxn];
bool cmp(int a,int b){
    return a>b;
}
deque<int>tj,qw;
int main(){
    cin>>n;
    for(int i(1);i<=n;i++){
        cin>>a[i];
    }
    for(int i(1);i<=n;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i(1);i<=n;i++){
        tj.push_back(a[i]);
        qw.push_back(b[i]);
    }
    while(tj.size()&&qw.size()){
        if(tj.front()>qw.front()){
            ans++;
            tj.pop_front();
            qw.pop_front();
        }else if(tj.back()>qw.back()){
            ans++;
            tj.pop_back();
            qw.pop_back();
        }else{
            if(tj.back()<qw.front()){
                ans--;
            }
            tj.pop_back();
            qw.pop_front();
        }
    }
    cout<<ans*200<<'\n';
    return 0;
}