用奇怪的方法卡到了TLE90分

回复帖子

@Schwarzkopf_Henkal  2020-09-15 16:34 回复

RT,#9T了,不能AC有什么用啊

思路是用两遍2-pointers,先按x排序,求出可行的最右边的元素,然后把元素加到堆里面,堆的排序标准是y,然后堆内再来一遍2-pointers求出可行的最右边的元素,顺便维护sum,更新ans。

在学校OJ的没有多组数据的版本上过了,问一下能不能再优化一下过了这道题还是就翻不了身了

#include<bits/stdc++.h>
using namespace std;
int t;
int n,w,h,mk[10005],ans;
struct node{
    int x,y,a;
    friend bool operator<(node u,node v){
        return u.y<v.y;
    }
}c[10005];
multiset<node>mts;
typedef multiset<node>::iterator iter;
bool cmp(node a,node b){
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(mk,0,sizeof(mk));
        mts.clear();
        ans=0;
        scanf("%d%d%d",&n,&w,&h);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].a);
        sort(c+1,c+n+1,cmp);
        mts.insert(c[0]);
        for(int i=1,r=0;i<=n;i++){
            mts.erase(mts.find(c[i-1]));
            while(r<n&&c[r+1].x<=c[i].x+w-1){
                r++;
                mts.insert(c[r]);
            }
            if(mk[r])
                continue;
            mk[r]=1;
            iter itl=mts.begin(),itr=mts.begin();
            int sum=itl->a;
            while(itl!=mts.end()){
                while(1){
                    iter it=itr;   
                    it++;
                    if(it==mts.end()||it->y>itl->y+h-1)
                        break;
                    itr=it;
                    sum+=itr->a;
                }
                ans=max(ans,sum);
                sum-=itl->a;
                itl++;
            }
        }
        printf("%d\n",ans);
    }
}/*
全部都是看起来不可做的题……
按x排序,以y作为第二关键字排序之后
对于某个点i,我们能做到直接找出对于最右边的一个还在范围里面的点。
可以证明这样一定是最优的。
如果我们另外来一个堆能维护……
再用一遍2-pointer
我担心堆的遍历复杂度会把我卡掉咯
*/
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。