P1081 [noip2012 improvement group] driving trip (doubling)

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

本文一共[544]字,预计阅读时长:1分钟~
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.
版权声明:本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢。 https://car.inotgo.com/2021/08/20210810065944672E.html