题解：P13316 [GCJ 2012 #1A] Kingdom Rush

· · 题解

背景

对不起审核大大，以前从来没写过题解，接连犯了好多错。。。

今年的普及组全机房就本蒟蒻没过呜呜,难受的我决定惩罚自己刷一百道题，结果一共就 AC 两道。。。但偶然间瞅到这道题居然可以写题解！！！

于是呢，就有了本蒟蒻的第一篇题解 hh。

分析

看到至少需要通关多少次，考虑排序和贪心。

使用两个结构体 one 和 two 分别存储关卡的两个难度条件，w 数组记录每个关卡的完成状态（由于有多组数据，所以每次读取下一组数据时 w 数组要清零）。

排序

优先尝试完成第二条件要求的关卡（奖励更高），当第二条件不满足时，转而完成第一条件要求的关卡。

所以两颗星星的情况从小到大排就好啦，但一颗星星的情况要注意：定义一个 sum 表示 Ryan 此时得到的星星数，如果 sum 满足以一星的成绩通过下一关，就去判断能否以现有的 sum 通过更高条件的以两星通过的关卡，否则就把剩下的关卡按照以一星完成所需的星星数从小到大排起来。

记得每次操作后重新排序剩余关卡，不然顺序就乱了。

贪心

使用双指针分别遍历两个排序后的关卡，实时更新当前所得的星星数 sum 作为通关判断的依据，并且要记录每个关卡的完成进度 w[id]。

AC代码


#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int t,sum,w[N];
struct one{
    int _1,_2,id;
}l1[N];
struct two{
    int _2,id;
}l2[N];

bool cmp1(one x,one y){
    if(sum>=x._1&&sum>=y._1)    return x._2>y._2;
    return x._1<y._1;
}//1星
bool cmp2(two x,two y){
    return x._2<y._2;
}//2星
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    int k=0;
    while(t--){
        int n,ans=0;
        sum=0;
        cin>>n;
        memset(w,0,sizeof(w));//清零
        for(int i=1;i<=n;i++){
            cin>>l1[i]._1>>l2[i]._2;
            l1[i]._2=l2[i]._2;
            l1[i].id=i;
            l2[i].id=i;
        }
        sort(l1+1,l1+1+n,cmp1);//先排1星
        sort(l2+1,l2+1+n,cmp2);//再排2星

        int x1=1,x2=1;//开贪
        bool f=0;
        while(x2<=n){
            bool _f=0;
            if(sum>=l2[x2]._2){
                sum+=(2-w[l2[x2].id]);
                w[l2[x2].id]=2;
                _f=1;
                x2++;
                ans++;
            }else{
                if(sum>=l1[x1]._1&&x1<=n){//这里卡了好久，一定要判断x1值域，不然会爆TAT
                    if(w[l1[x1].id]==0){
                        w[l1[x1].id]=1;
                        sum++;
                        ans++;
                    }
                    x1++;
                    _f=1;
                }
            }
            sort(l1+x1,l1+1+n,cmp1);//重新排
            if(!_f){
                cout<<"Case #"<<++k<<": Too Bad\n";
                f=1;
                break;
            }//此关卡无法通过
        }
        if(f)   continue;
        cout<<"Case #"<<++k<<": "<<ans<<"\n";//此关卡可通过
    }
    return 0;//完结撒花(OvO)
}