### P1081 [noip2012 improvement group] driving trip (doubling)

wx6110fa547fd20 2021-08-10 07:01:13 阅读数:455

p1081 noip2012 noip improvement group
P1081 [NOIP2012 Improvement group ] Travel by car ( Multiply )

Ideas

It's hard to imagine ！ First of all, the choice of this question is not strategic , namely A,B The next step from anywhere is unique .

That is, we have to preprocess A,B The next location from each city , about A It's the second smallest value to the right , Yes B It is the minimum value to the right .

A good practice is to sort first , We record who is on the left and right of each number , Because they are candidates for the minimum , Then follow the subscript from left to right , For the current first , Obviously left or right exists , Just choose the small one , For this small value of the current position , If the minimum value is left , Just take the left and right of the left to take the smallest , Otherwise, take the left and right, and the right takes the smallest , After each calculation To delete this number , If the current position of l exist ,l The right side of the is marked as r, In the current position r Existential empathy . In this way, you can delete a number .

Then there is multiplication preprocessing , If you want to query, double the number of rounds , Finally, I made a special judgment A Can you take another step .

See code for details .

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
ll A[N][20],B[N][20];
int f[N][20];
struct node{
int h,l,r,id;
bool operator<(const node &a) const{
return h<a.h;
}
}a[N];
int n;
ll x0;
int m;
ll sa,sb;
int na[N],nb[N];// next position
void init(){
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
A[i][j]=A[i][j-1]+A[f[i][j-1]][j-1];
B[i][j]=B[i][j-1]+B[f[i][j-1]][j-1];
}
}
bool ck(int l,int r,int p){
if(!l) return 0;
if(!r) return 1;
return a[p].h-a[l].h<=a[r].h-a[p].h;
}
int cx(int l,int r,int p){
if(!l) return a[r].id;
if(!r) return a[l].id;
return a[p].h-a[l].h<=a[r].h-a[p].h?a[l].id:a[r].id;
}
void fun(ll x,int p){
sa=sb=0;
for(int i=19;~i;i--){
if(f[p][i]&&sa+sb+A[p][i]+B[p][i]<=x){
sa+=A[p][i];
sb+=B[p][i];
p=f[p][i];
}
}
if(na[p]&&sa+sb+A[p][0]<=x) sa+=A[p][0];
}
int mp[N];
void solve(){
//think twice code once
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].h),a[i].id=i;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) a[i].l=i-1,a[i].r=i+1;
a[1].l=a[n].r=0;
for(int i=1;i<=n;i++) mp[a[i].id]=i;
for(int i=1;i<=n;i++){
int j=mp[i];int l=a[j].l,r=a[j].r;
if(ck(l,r,j)) nb[i]=a[l].id,na[i]=cx(a[l].l,r,j);
else nb[i]=a[r].id,na[i]=cx(l,a[r].r,j);
if(l) a[l].r=r;
if(r) a[r].l=l;
}
for(int i=1;i<=n;i++){
f[i][0]=nb[na[i]];
A[i][0]=abs(a[mp[i]].h-a[mp[na[i]]].h);
B[i][0]=abs(a[mp[f[i][0]]].h-a[mp[na[i]]].h);
//printf("%d %lld %lld\n",f[i][0],A[i][0],B[i][0]);
}
init();
scanf("%lld%d",&x0,&m);
double mn=1e18;
int id=-1;
for(int i=1;i<=n;i++){
fun(x0,i);
if(sb&&1.0*sa/sb<mn){
id=i;
mn=1.0*sa/sb;
}
}
printf("%d\n",id);
while(m--){
ll x;int p;
scanf("%d%lld",&p,&x);
fun(x,p);
printf("%lld %lld\n",sa,sb);
}
}
int main(){
solve();
return 0;
}

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.
• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.
• 31.
• 32.
• 33.
• 34.
• 35.
• 36.
• 37.
• 38.
• 39.
• 40.
• 41.
• 42.
• 43.
• 44.
• 45.
• 46.
• 47.
• 48.
• 49.
• 50.
• 51.
• 52.
• 53.
• 54.
• 55.
• 56.
• 57.
• 58.
• 59.
• 60.
• 61.
• 62.
• 63.
• 64.
• 65.
• 66.
• 67.
• 68.
• 69.
• 70.
• 71.
• 72.
• 73.
• 74.
• 75.
• 76.
• 77.
• 78.
• 79.
• 80.
• 81.
• 82.
• 83.
• 84.
• 85.
• 86.
• 87.
• 88.
• 89.
• 90.
• 91.
• 92.
• 93.
• 94.
• 95.
• 96.
• 97.
• 98.
• 99.
• 100.
• 101.
• 102.
• 103.
• 104.
• 105.