NOIP2012开车旅行

描述

小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i 的海拔高度为Hi，城市i 和城市j 之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j] = |Hi – Hj|。

旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出X公里，他们就会结束旅行。
在启程之前，小A想知道两个问题：
1．对于一个给定的X=X0，从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（如果小B的行驶路程为0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2. 对任意给定的X=Xi 和出发城市Si，小A开车行驶的路程总数以及小B行驶的路程总数。

格式

输入格式

第一行包含一个整数N，表示城市的数目。
第二行有N个整数，每两个整数之间用一个空格隔开，依次表示城市1到城市N的海拔高度，即H1，H2，……，Hn，且每个Hi 都是不同的。
第三行包含一个整数X0。
第四行为一个整数M，表示给定M组Si和Xi。
接下来的M行，每行包含2个整数Si 和Xi，表示从城市Si 出发，最多行驶Xi 公里。

输出格式

输出共M+1行。
第一行包含一个整数S0，表示对于给定的X0，从编号为S0的城市出发，小A开车行驶
的路程总数与小B行驶的路程总数的比值最小。
接下来的M行，每行包含2个整数，之间用一个空格隔开，依次表示在给定的Si 和Xi 下小A行驶的里程总数和小B行驶的里程总数。

样例1

样例输入1[复制]

4 2 3 1 4 3 4 1 3 2 3 3 3 4 3

1
2
3
4
5
6
7
8

4
2 3 1 4
3
4
1 3
2 3
3 3
4 3

样例输出1[复制]

1 1 1 2 0 0 0 0 0

1
2
3
4
5

1
1 1
2 0
0 0
0 0

样例2

样例输入2[复制]

10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14

10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

样例输出2[复制]

2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0

1
2
3
4
5
6
7
8
9
10
11

2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

限制

每个测试点1s

提示

对于30%的数据，有1≤N≤20，1≤M≤20；
对于40%的数据，有1≤N≤100，1≤M≤100；
对于50%的数据，有1≤N≤100，1≤M≤1,000；

对于70%的数据，有1≤N≤1,000，1≤M≤10,000；
对于100%的数据，有1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证Hi 互不相同。

题解

表示vijos数据太强，我蛋都碎了。。。根本AC无能

说说做法吧T T

用平衡树处理出每个点开始小A/小B能到达的下个点，然后加个倍增就行了T T

第一问枚举起点即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define inf 5000000000LL
#define ll long long 
using namespace std;
const double pi=acos(-1.0);
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int n,x0,m;
int h[100005];
ll a[100005],b[100005],va[100005][17],vb[100005][17];
int fa[100005],fb[100005],to[100005][17];
set<ll> q;
map<ll,int> mp;
struct data{ll h,key;}t[5];
inline bool operator<(data a,data b)
{
    return a.key<b.key||(a.key==b.key&&a.h<b.h);
}
void pre()
{
    for(int i=n;i;i--)
    {
        q.insert(h[i]);
        t[1].h=*--q.lower_bound(h[i]),t[2].h=*q.upper_bound(h[i]);
        if(t[1].h!=-inf)t[3].h=*--q.lower_bound(t[1].h);
		else t[3].h=-inf;
		if(t[2].h!=inf)t[4].h=*q.upper_bound(t[2].h);
		else t[4].h=inf;
        for(int k=1;k<=4;k++)
            t[k].key=abs(t[k].h-h[i]);
        sort(t+1,t+5);
        a[i]=t[2].key;fa[i]=mp[t[2].h];
        b[i]=t[1].key;fb[i]=mp[t[1].h];
        for(int j=0;j<=16;j++)
            if(j==0)
            {
                if(fa[i]){va[i][0]=a[i];to[i][0]=fa[i];}
            }
            else if(j==1)
            {
                if(fb[fa[i]]){va[i][1]=a[i];vb[i][1]=b[fa[i]];to[i][1]=fb[fa[i]];}
            }
            else if(to[to[i][j-1]][j-1])
            {
                va[i][j]=va[i][j-1]+va[to[i][j-1]][j-1];
                vb[i][j]=vb[i][j-1]+vb[to[i][j-1]][j-1];
                to[i][j]=to[to[i][j-1]][j-1];
            }
			else break;
    }
}
double cal1(int x,int val)
{
    int t1=0,t2=0;
    for(int i=16;i>=0;i--)
        if(to[x][i]&&t1+va[x][i]+t2+vb[x][i]<=val)
        {
            t1+=va[x][i];t2+=vb[x][i];
            x=to[x][i];
        }
	if(t2==0)return inf;
    return (double)t1/(double)t2;
}
void cal2(int x,int val)
{
    int t1=0,t2=0;
    for(int i=16;i>=0;i--)
        if(to[x][i]&&t1+va[x][i]+t2+vb[x][i]<=val)
        {
            t1+=va[x][i];t2+=vb[x][i];
            x=to[x][i];
        }
    printf("%d %d\n",t1,t2);
}
void solve1()
{
    double mn=1e60;int ans;
    x0=read();
    for(int i=1;i<=n;i++)
    {
        double t=cal1(i,x0);
        if(t<mn||(t==mn&&h[i]>h[ans]))
        {
            mn=t;ans=i;
        }
    }
    printf("%d\n",ans);
}
void solve2()
{
    m=read();
    for(int i=1;i<=m;i++)
    {
        int s=read(),x=read();
        cal2(s,x);
    }
}
int main()
{
    n=read();
    q.insert(-inf);q.insert(inf);
    for(int i=1;i<=n;i++)
    {
        h[i]=read();
        mp[h[i]]=i;
    }
    pre();
    solve1();
    solve2();
    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

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<cmath>

#include<algorithm>

#include<map>

#define inf 5000000000LL

#define ll long long

using namespace std;

const double pi=acos(-1.0);

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[20];

int n,x0,m;

int h[100005];

ll a[100005],b[100005],va[100005][17],vb[100005][17];

int fa[100005],fb[100005],to[100005][17];

set<ll> q;

map<ll,int> mp;

struct data{ll h,key;}t[5];

inline bool operator<(data a,data b)

{

return a.key<b.key||(a.key==b.key&&a.h<b.h);

}

void pre()

{

for(int i=n;i;i--)

{

q.insert(h[i]);

t[1].h=*--q.lower_bound(h[i]),t[2].h=*q.upper_bound(h[i]);

if(t[1].h!=-inf)t[3].h=*--q.lower_bound(t[1].h);

else t[3].h=-inf;

if(t[2].h!=inf)t[4].h=*q.upper_bound(t[2].h);

else t[4].h=inf;

for(int k=1;k<=4;k++)

t[k].key=abs(t[k].h-h[i]);

sort(t+1,t+5);

a[i]=t[2].key;fa[i]=mp[t[2].h];

b[i]=t[1].key;fb[i]=mp[t[1].h];

for(int j=0;j<=16;j++)

if(j==0)

{

if(fa[i]){va[i][0]=a[i];to[i][0]=fa[i];}

}

else if(j==1)

{

if(fb[fa[i]]){va[i][1]=a[i];vb[i][1]=b[fa[i]];to[i][1]=fb[fa[i]];}

}

else if(to[to[i][j-1]][j-1])

{

va[i][j]=va[i][j-1]+va[to[i][j-1]][j-1];

vb[i][j]=vb[i][j-1]+vb[to[i][j-1]][j-1];

to[i][j]=to[to[i][j-1]][j-1];

}

else break;

}

double cal1(int x,int val)

{

int t1=0,t2=0;

for(int i=16;i>=0;i--)

if(to[x][i]&&t1+va[x][i]+t2+vb[x][i]<=val)

{

t1+=va[x][i];t2+=vb[x][i];

x=to[x][i];

}

if(t2==0)return inf;

return (double)t1/(double)t2;

}

void cal2(int x,int val)

{

int t1=0,t2=0;

for(int i=16;i>=0;i--)

if(to[x][i]&&t1+va[x][i]+t2+vb[x][i]<=val)

{

t1+=va[x][i];t2+=vb[x][i];

x=to[x][i];

}

printf("%d %d\n",t1,t2);

}

void solve1()

{

double mn=1e60;int ans;

x0=read();

for(int i=1;i<=n;i++)

{

double t=cal1(i,x0);

if(t<mn||(t==mn&&h[i]>h[ans]))

{

mn=t;ans=i;

}

printf("%d\n",ans);

}

void solve2()

{

m=read();

for(int i=1;i<=m;i++)

{

int s=read(),x=read();

cal2(s,x);

}

int main()

{

n=read();

q.insert(-inf);q.insert(inf);

for(int i=1;i<=n;i++)

{

h[i]=read();

mp[h[i]]=i;

}

pre();

solve1();

solve2();

return 0;

}

hzwer.com _ Home | http://hzwer.com

描述

格式

输入格式

输出格式

样例1

样例输入1[复制]

样例输出1[复制]

样例2

样例输入2[复制]

样例输出2[复制]

限制

提示

分类目录

热门文章

Myfriends

近期评论