题解：P10728 [NOISG 2023 Qualification] Swords

Danny_chan · 2024-07-09 19:54:16 · 题解

因为本题数据有点大，用双重循环不能过，所以我们要考虑优化。可以先把攻击力和防御能力用结构体存起来再按攻击力排序，然后再从排序过的数据开始枚举，如果这把剑的防御能力大于之前最大的防御能力，那么这个就是有用的剑，把答案数量加一再更新最大的防御能力就大功告成了！

代码：

#include<bits/stdc++.h>
using namespace std;
int n,sum=0,maxx=-1e9;
struct s{
    int a,b;
}q[100010];
bool cmp(s x,s y){
    if(x.a!=y.a) return x.a>y.a;
    else return x.b>y.b;
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i].a>>q[i].b;
    }
    sort(q+1,q+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(q[i].b>maxx){
            sum++;
            maxx=q[i].b;
        }
    }
    cout<<sum<<endl;
    return 0; 
}