| 记录编号 |
72861 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[NOIP 2012]开车旅行 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.854 s |
| 提交时间 |
2013-10-19 12:10:39 |
内存使用 |
62.26 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<list>
#include<set>
#include<map>
#include<cmath>
using namespace std;
//A选择第二近,B选择最近
//我的x,s和题目是反着的orz
const int SIZEN=100001,MAXIND=17;
typedef long long ll;
int n;//城市数
int nowind;
int h[SIZEN]={16};//每个城市的高度
class JUMP{
public:
int des;//目的地
int ad;//A开的长度
int bd;//B开的长度
int sd;//总共的长度
int fdr;//终点时的驾驶员
JUMP(){
des=ad=bd=sd=fdr=0;
}
};
JUMP operator + (JUMP x,JUMP y){//这个操作是有向的,即:走完x表示的行程再接着走y表示的行程
JUMP ans;
ans.des=y.des;
ans.ad=x.ad+y.ad;
ans.bd=x.bd+y.bd;
ans.sd=x.sd+y.sd;
ans.fdr=y.fdr;
return ans;
}
class CITY{
public:
int pos;
int alt;//海拔
};
bool operator < (CITY a,CITY b){
if(a.alt<b.alt) return true;
if(a.alt>b.alt) return false;
return a.pos<b.pos;
}
class CITY_DELTA{
public:
int pos;
int dalt;//海拔之差
int alt;//海拔
};
bool operator < (CITY_DELTA a,CITY_DELTA b){
if(a.dalt<b.dalt) return true;
if(a.dalt>b.dalt) return false;
if(a.alt<b.alt) return true;
if(a.alt>b.alt) return false;
return a.pos<b.pos;
}
JUMP f[2][SIZEN][MAXIND];//0代表a,1代表b
int pow_2_list[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};
int pow2(int x){
return pow_2_list[x];
}
JUMP limited_drive(int x,int s,int dr){//从城市x出发,行程最高s,驾驶员为dr,最终的结果
int i=0;
#define next f[dr][x][i]
if(next.des&&s>=next.sd){
while(next.des&&s>=next.sd) i++;
i--;
return next+limited_drive(next.des,s-next.sd,next.fdr);//可走
}
JUMP ans;
return ans;//就是return了个零变量
}
void init_one_jump(void){
set<CITY> cst;
set<CITY>::iterator ckey,ckey1;
int i;
for(i=1;i<=n;i++) cst.insert((CITY){i,h[i]});
set<CITY_DELTA> cdst;
set<CITY_DELTA>::iterator cdkey;
for(i=1;i<=n;i++){
cdst.clear();
ckey=cst.find((CITY){i,h[i]});
ckey1=ckey;
if(ckey!=cst.begin()){
ckey--;
cdst.insert((CITY_DELTA){ckey->pos,abs(ckey->alt-h[i]),ckey->alt});
if(ckey!=cst.begin()){
ckey--;
cdst.insert((CITY_DELTA){ckey->pos,abs(ckey->alt-h[i]),ckey->alt});
}
}
ckey=ckey1;
ckey++;
if(ckey!=cst.end()){
cdst.insert((CITY_DELTA){ckey->pos,abs(ckey->alt-h[i]),ckey->alt});
ckey++;
if(ckey!=cst.end()) cdst.insert((CITY_DELTA){ckey->pos,abs(ckey->alt-h[i]),ckey->alt});
}
if(!cdst.empty()){
cdkey=cdst.begin();
f[1][i][0].des=cdkey->pos;
f[1][i][0].ad=0;
f[1][i][0].bd=cdkey->dalt;
f[1][i][0].sd=cdkey->dalt;
f[1][i][0].fdr=0;
cdst.erase(cdkey);
}
if(!cdst.empty()){
cdkey=cdst.begin();
f[0][i][0].des=cdkey->pos;
f[0][i][0].ad=cdkey->dalt;
f[0][i][0].bd=0;
f[0][i][0].sd=cdkey->dalt;
f[0][i][0].fdr=1;
}
cst.erase(ckey1);
}
}
void init_jumps(void){
int i,j;
#define next0 f[0][i][j-1]
#define next1 f[1][i][j-1]
for(j=1;j<=nowind;j++){
for(i=1;i<=n;i++){//此处,由于fa,fb中多余变量均初始化为0,故"溢出"不会产生影响
f[0][i][j]=next0+f[next0.fdr][next0.des][j-1];
f[1][i][j]=next1+f[next1.fdr][next1.des][j-1];
}
}
}
bool better(JUMP x,int xs,JUMP y,int ys){//x的选择优于y的选择,是则true
if(y.bd==0){
if(x.bd>0) return true;
if(h[xs]>h[ys]) return true;
return false;
}
if(x.bd==0){
if(y.bd>0) return false;
if(h[xs]>h[ys]) return true;
return false;
}
if(ll(x.ad)*ll(y.bd)<ll(x.bd)*ll(y.ad)) return true;
if(ll(x.ad)*ll(y.bd)>ll(x.bd)*ll(y.ad)) return false;
if(h[xs]>h[ys]) return true;
return false;
}
void calc_jumps(void){
int m;
scanf("%d",&m);
int i,x,s;
JUMP now;
for(i=1;i<=m;i++){
scanf("%d%d",&x,&s);
now=limited_drive(x,s,0);
printf("%d %d\n",now.ad,now.bd);
}
}
void best_choice(void){
int s;
JUMP ans,now;
int ans_start;
scanf("%d",&s);
ans=limited_drive(1,s,0);
ans_start=1;
int i;
for(i=2;i<=n;i++){
now=limited_drive(i,s,0);
if(better(now,i,ans,ans_start)){
ans=now;
ans_start=i;
}
}
printf("%d\n",ans_start);
}
void read(void){
scanf("%d",&n);
nowind=int(log((double)n)/log(2.0));
int i;
for(i=1;i<=n;i++) scanf("%d",&h[i]);
}
int main(){
freopen("drive.in","r",stdin);
freopen("drive.out","w",stdout);
read();
init_one_jump();
init_jumps();
best_choice();
calc_jumps();
return 0;
}