小小小朋友的小小世界

题目描述

给出n个直线，求有多少个能够在某个时刻最高。

很明显是一个单调栈的题目……不应该评到紫的。

思路

这道题本意显然不是让你写平方暴力的……但是这个题的的数据过于水了，很多有一些问题的代码都能通过。据我旁边的同学说，他把大部分题解测了一下，发现有很多问题。

稍微强一点的

我们按照距离从大到小排序，挨个入栈，显然距离和速度都比栈顶小的没有用了。

其次我们看当前栈顶元素超过栈中第二个元素的时间。

如果说当前要插入的这个元素和栈顶相遇（或者理解为超过栈顶）要早于这个时间，那么可以发现栈顶元素是永无出头之日的，可以出栈。

我们可以写分数来避免精度问题（当然好像不写问题也不大）

还要注意特判掉两个元素完全相同，这个时候我们把刚才的元素再入栈就行了。

有些细节可以看代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct frac{//分数
    int x,y;
    void yf(){
        if(x==0||y==0) return;
        int p=__gcd(x,y);
        x/=p;y/=p;
    }
    frac(int a,int b){x=a;y=b;yf();}
    frac(){x=0;y=1;}
    bool operator<(const frac &b)const{
        return x*b.y<y*b.x;
    }
};
struct node{
    int id,x,y;
    frac t;
    bool operator<(const node &b)const{
        if(x==b.x) return y<b.y;
        return x>b.x;
    }
};
node a[1000005];
deque<node> v;
signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<n;i++){cin>>a[i].x;a[i].id=i;}
    for(int i=0;i<n;i++){cin>>a[i].y;}
    sort(a,a+n);
    a[0].t=frac(0,1);
    v.push_back(a[0]);
    for(int i=1;i<n;i++){
        if(!v.empty()&&a[i].x==v.back().x&&a[i].y==v.back().y){//判掉完全相同
            v.push_back((node){a[i].id,a[i].x,a[i].y,v.back().t});
            continue;
        }
        if(!v.empty()&&a[i].y<=v.back().y) continue;//判掉打不过
        while(!v.empty()&&frac(v.back().x-a[i].x,a[i].y-v.back().y)<v.back().t){//把永无出头之日的栈顶删掉
            v.pop_back();
        }
        v.push_back((node){a[i].id,a[i].x,a[i].y,frac(v.back().x-a[i].x,a[i].y-v.back().y)});//入栈，记录下与栈顶的元素相遇时间用于比较
    }
    cout<<v.size()<<endl;
    vector<int> ans;
    while(!v.empty()){
        ans.push_back(v.front().id+1);
        v.pop_front();
    }
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';
    return 0;
}