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
我担心堆的遍历复杂度会把我卡掉咯
*/