题解归档 - cf535E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf535E
• 本地来源：problems/cf535E/idea.md
• 题目链接：https://codeforces.com/contest/535/problem/E
• 原始标题：CF535E — Tavas and Pashmaks

思路

CF535E — Tavas and Pashmaks

题意

$n$ 名选手，第 $i$ 人游泳速度 $s_i$、跑步速度 $r_i$。比赛先游 $S$ 米再跑 $R$ 米（$S,R>0$ 未知）。总用时 $T_i=S/s_i+R/r_i$。若存在某组 $(S,R)$ 使 $i$ 并列最优，则 $i$「可能夺冠」。输出所有可能夺冠者的编号（升序）。

做法

令 $w=S/R>0$，则 $T_i=R(w/s_i+1/r_i)$，比较 $f_i(w)=w/s_i+1/r_i$ 即可。

支配剔除：若存在 $j$ 满足 $s_j\ge s_i$ 且 $r_j\ge r_i$ 且至少一处严格，则 $i$ 永不可能最优（游泳、跑步都不占优）。

凸包：在 $(s,r)$ 平面上，将未被支配的点按 $s$ 升序做上凸壳（cross<0 时弹栈，共线保留）。凸壳上的点恰对应存在某个 $w$ 使该点 $f_i$ 最小的选手；共线边界上多点均可夺冠。

复杂度 $O(n\log n)$。

验证

• 样例 1：三点共线于帕累托前沿，输出 1 2 3。
• 样例 2：$(1,1)$ 被 $(1,2)$ 支配；$(1,2)$ 与 $(2,1)$ 在 $S\le R$ / $S\ge R$ 各占优，输出 1 3。
• stress.py 对小 $n$ 区间可行性暴力对拍 500 组通过。

代码

来源：problems/cf535E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:24:25
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct pt{
    ll s,r,id;
};
vector<pt>a,b,hull;
ll cross(pt o,pt p,pt q){
    return (p.s-o.s)*(q.r-o.r)-(p.r-o.r)*(q.s-o.s);
}
int main(){
    ll n,i,j,k,zc,pd,cur,dq,cnt,ans,mxr,ls;
    cin>>n;
    a.resize(n);
    for(i=0;i<n;i++){
        cin>>a[i].s>>a[i].r;
        a[i].id=i+1;
    }
    sort(a.begin(),a.end(),[](pt x,pt y){
        if(x.s!=y.s) return x.s>y.s;
        return x.r>y.r;
    });
    b.clear();
    mxr=-1,ls=-1;
    for(i=0;i<n;i++){
        if(a[i].r>mxr or (a[i].r==mxr and a[i].s==ls)){
            b.push_back(a[i]);
            if(a[i].r>mxr){
                mxr=a[i].r;
                ls=a[i].s;
            }
        }
    }
    sort(b.begin(),b.end(),[](pt x,pt y){
        return x.s<y.s;
    });
    hull.clear();
    for(i=0;i<(ll)b.size();i++){
        while((ll)hull.size()>=2 and cross(hull[(ll)hull.size()-2],hull[(ll)hull.size()-1],b[i])<0) hull.pop_back();
        hull.push_back(b[i]);
    }
    for(i=0;i<(ll)hull.size();i++){
        if(i) cout<<" ";
        cout<<hull[i].id;
    }
    cout<<"\n";
    return 0;
}