题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因(初次提交分数) |
---|---|---|---|---|---|
Bonnie and Clyde | ★★☆☆☆ | 答案正确 | 100 | 2015-2-21 20:28:56 | 边界条件(2) |
(AC 456)
给出数轴上若干点的坐标和价值,求坐标相差≥d的两点之和的最大值。
531.cpp代码已折叠
展开折叠内容
|
---|
#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; #define si(n) scanf("%d",&n) #define ci const int & #define dsi(n) int n;si(n) #define f(i,n) for(int i=1;i<=n;++i) #define fi(i,p,n) for(int i=p;i<=n;++i) #define fd(i,n) for(int i=n;i!=0;--i) #define fdi(i,p,n) for(int i=n;i>=p;--i) int countS[3]={},maxA=0,b=0; class st { public: int a,d,i,j; st():a(0),d(0),i(0),j(0){}; st(ci _i,ci _j,ci _d):i(_i),j(_j),d(_d){}; st(ci _i,ci _d):i(_i),d(_d){}; friend bool operator <(const st&a,const st&b){return a.d<b.d;} } p[200010]={},ans=st(-1,-1,-1),preMax[200010]={}; int main() { dsi(n); dsi(D); int j=1; f(i,n) { si(p[i].d); si(p[i].a); p[i].i=i; } sort(p+1,p+n+1); p[0].d=1e+8;//fixed:边界条件// f(i,n) { preMax[i]=max(preMax[i-1],st(p[i].i,p[i].i,p[i].a)); while(p[i].d-p[j].d>=D)++j; if(p[i].d-p[j-1].d>=D) --j,ans=max(ans,st(p[i].i,preMax[j].i,p[i].a+preMax[j].d)); } printf("%d %d",ans.i,ans.j); return 0; } |