C++(g++ 7.5.0) 解法, 执行用时: 202ms, 内存消耗: 80328K, 提交时间: 2022-08-11 16:30:27
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100010;
struct node{
int id,v,l,r;
bool operator < (const node &a) const{
return v<a.v;
}
}d[maxn];
int sta[maxn][31],stb[maxn][31],f[maxn][31],n,p[maxn],na[maxn],nb[maxn];
double minn=2147483647;
inline bool lf(int now,int l,int r){
if(!l) return 0;
if(!r) return 1;
return d[now].v-d[l].v<=d[r].v-d[now].v;
}
inline int zzz(int now,int x,int y){
if(!x) return d[y].id;
if(!y) return d[x].id;
if(d[now].v-d[x].v<=d[y].v-d[now].v) return d[x].id;
return d[y].id;
}
inline void stwork(){
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
sta[i][j]=sta[i][j-1]+sta[f[i][j-1]][j-1];
stb[i][j]=stb[i][j-1]+stb[f[i][j-1]][j-1];
}
}
int a,b;
inline void gtab(long long x,int p){
a=b=0;
for(int i=19;i>=0;i--)
if(f[p][i] && (long long)(a+b+sta[p][i]+stb[p][i])<=x){
a+=sta[p][i];
b+=stb[p][i];
p=f[p][i];
}
if(na[p] && a+b+sta[p][0]<=x) a+=sta[p][0];
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&d[i].v);
for(int i=1;i<=n;i++)
d[i].id=i;
sort(d+1,d+1+n);
for(int i=1;i<=n;i++)
p[d[i].id]=i;
for(int i=1;i<=n;i++)
d[i].l=i-1,d[i].r=i+1;
d[1].l=d[n].r=0;
for(int i=1;i<=n;i++){
int now=p[i],l=d[now].l,r=d[now].r;
if(lf(now,l,r)) nb[i]=d[l].id,na[i]=zzz(now,d[l].l,r);
else nb[i]=d[r].id,na[i]=zzz(now,l,d[r].r);
if(l) d[l].r=r;
if(r) d[r].l=l;
}
for(int i=1;i<=n;i++){
f[i][0]=nb[na[i]];
sta[i][0]=abs(d[p[i]].v-d[p[na[i]]].v);
stb[i][0]=abs(d[p[f[i][0]]].v-d[p[na[i]]].v);
}
stwork();
int x,m,ans,y;
scanf("%lld%lld",&x,&m);
for(int i=1;i<=n;i++){
gtab(x,i);
if(b && 1.0*a/b < minn)
minn=1.0*a/b,ans=i;
}
printf("%lld\n",ans);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
gtab(y,x);
printf("%lld %lld\n",a,b);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 387ms, 内存消耗: 78308K, 提交时间: 2019-11-20 22:25:05
#include<iostream>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
const int INF = 0x7fffffff;
const int maxn = 1e5 + 100;
typedef long long LL;
struct note{
LL h,_abs;
}t[5];
set<LL>s;
map<LL,LL>mp;
LL n,h[maxn],a[maxn],b[maxn],fa[maxn],fb[maxn],sa[maxn][25],sb[maxn][25],f[maxn][25];
bool cmp(note aa,note bb)
{
return (aa._abs==bb._abs?aa.h<bb.h:aa._abs<bb._abs);
}
void st()
{
for(LL i=n;i>=1;i--)
{
s.insert(h[i]);
t[1].h = *--s.lower_bound(h[i]);
t[3].h = *--s.lower_bound(t[1].h);
t[2].h = *s.upper_bound(h[i]);
t[4].h = *s.upper_bound(t[2].h);
for(LL j=1;j<=4;j++)
t[j]._abs = abs(t[j].h-h[i]);
sort(t+1,t+5,cmp);
a[i] = t[2]._abs;
fa[i] = mp[t[2].h];
b[i] = t[1]._abs;
fb[i]= mp[t[1].h];
if(fa[i])
{
sa[i][0] = a[i];
f[i][0] = fa[i];
}
if(fb[fa[i]])
{
sa[i][1] = a[i];
sb[i][1] = b[fa[i]];
f[i][1] = fb[fa[i]];
}
for(LL j=2;j<=16;j++)
if(f[ f[i][j-1] ][j-1])
{
sa[i][j] = sa[i][j-1] + sa[f[i][j-1]][j-1];
sb[i][j] = sb[i][j-1] + sb[f[i][j-1]][j-1];
f[i][j] = f[f[i][j-1]][j-1];
}
else break;
}
}
double ask1(LL x,LL p)
{
LL s1 = 0,s2 = 0;
for(LL i=16;i>=0;i--)
{
if(f[x][i]&&s1+s2+sa[x][i]+sb[x][i]<=p)
{
s1 += sa[x][i];
s2 += sb[x][i];
x = f[x][i];
}
}
return s2==0?INF:(double)s1/(double)s2;
}
void ask2(LL x,LL p)
{
LL s1 = 0;
LL s2 = 0;
for(LL i=16;i>=0;i--)
if(f[x][i] && s1+s2+sa[x][i]+sb[x][i]<=p)
{
s1 += sa[x][i];
s2 += sb[x][i];
x = f[x][i];
}
if(fa[x]&&s1+s2+sa[x][0]<=p) s1 += sa[x][0];
printf("%lld %lld\n",s1,s2);
}
void solve()
{
double minn = INF;
LL bj,x0;
scanf("%lld",&x0);
for(LL i=1;i<=n;i++)
{
double op = ask1(i,x0);
if(op<minn)
{
minn = op;
bj = i;
}
}
printf("%lld\n",bj);
LL m,s0;
scanf("%lld",&m);
while(m--)
{
scanf("%lld%lld",&s0,&x0);
ask2(s0,x0);
}
}
int main()
{
s.insert(INF);
s.insert(INF-1);
s.insert(-INF);
s.insert(-INF+1);
scanf("%lld",&n);
for(LL i=1;i<=n;i++)
{
scanf("%lld",&h[i]);
mp[h[i]] = i;
}
st();
solve();
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 389ms, 内存消耗: 78200K, 提交时间: 2019-11-16 18:30:58
#include<bits/stdc++.h>
#define INF 50000000000LL
#define A 100005
using namespace std;
struct note{
long long h,_abs;
}t[5];
set<long long>s;
map<long long,long long>mp;
long long n,h[A],a[A],b[A],fa[A],fb[A],sa[A][25],sb[A][25],f[A][25];
bool cmp(note aa,note bb){
return (aa._abs==bb._abs?aa.h<bb.h:aa._abs<bb._abs);
}
void st(){
for(long long i=n;i>=1;i--){
s.insert(h[i]);
t[1].h=*--s.lower_bound(h[i]);
t[3].h=*--s.lower_bound(t[1].h);
t[2].h=*s.upper_bound(h[i]);
t[4].h=*s.upper_bound(t[2].h);
for(long long j=1;j<=4;j++)t[j]._abs=abs(t[j].h-h[i]);
sort(t+1,t+5,cmp);
a[i]=t[2]._abs;fa[i]=mp[t[2].h];
b[i]=t[1]._abs;fb[i]=mp[t[1].h];
// s.insert(h[i]);
if(fa[i])sa[i][0]=a[i],f[i][0]=fa[i];
if(fb[fa[i]])sa[i][1]=a[i],sb[i][1]=b[fa[i]],f[i][1]=fb[fa[i]];
for(long long j=2;j<=16;j++)
if(f[f[i][j-1]][j-1]){
sa[i][j]=sa[i][j-1]+sa[f[i][j-1]][j-1];
sb[i][j]=sb[i][j-1]+sb[f[i][j-1]][j-1];
f[i][j]=f[f[i][j-1]][j-1];
}
else break;
}
}
double ask1(long long x,long long p){
long long s1=0,s2=0;
for(long long i=16;i>=0;i--){
if(f[x][i]&&s1+s2+sa[x][i]+sb[x][i]<=p){
s1+=sa[x][i];
s2+=sb[x][i];
x=f[x][i];
}
}
return (s2==0?INF:(double)s1/(double)s2);
}
void ask2(long long x,long long p){
long long s1=0,s2=0;
for(long long i=16;i>=0;i--){
if(f[x][i]&&s1+s2+sa[x][i]+sb[x][i]<=p){
s1+=sa[x][i];
s2+=sb[x][i];
x=f[x][i];
}
}
if(fa[x]&&s1+s2+sa[x][0]<=p)s1+=sa[x][0];
printf("%lld %lld\n",s1,s2);
}
void solve(){
double minn=INF;
long long bj,x0;
scanf("%lld",&x0);
for(long long i=1;i<=n;i++){
double op=ask1(i,x0);
if(op<minn)minn=op,bj=i;
}
printf("%lld\n",bj);
long long m,s0;
scanf("%lld",&m);
while(m--){
scanf("%lld%lld",&s0,&x0);
ask2(s0,x0);
}
}
int main(){
s.insert(INF);s.insert(INF-1);s.insert(-INF);s.insert(-INF+1);
scanf("%lld",&n);
for(long long i=1;i<=n;i++)scanf("%lld",&h[i]),mp[h[i]]=i;
st();
solve();
return 0;
}
