本文主要是介绍题目1 : 打折机票(hihocoder 20挑战赛)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
-
7 6 1 1 2 1 4 3 4 4 4 5 6 9 7 9 1 7 1 2 6 7 3 3 4 4 5 5
样例输出 -
9 1 9 None 5 None
描述
因为思念新宿的"小姐姐"们，岛娘计划6月份再去一趟东京，不过这次看来她需要自掏腰包。经过了几天的夜战，岛娘终于在体力耗尽之前，用Python抓下了所有6月份，上海至东京的全部共 n 张机票。现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的，最贵的机票。
输入
输入数据的第一行包含两个整数 n, m(1 ≤ n, m ≤ 105)，分别表示机票的总数，和询问的总数。接下来的 n 行，每行两个整数 t, v (1 ≤ t, v ≤ 105)，表示每张机票出发的时间和价格。 接下来的 m 行，每行两个整数 a, b (1 ≤ a ≤ b ≤ 105)，表示每个询问所要求的时间区间。
输出
对于每组询问，输出一行表示最贵的价格。如果没有符合要求的机票，输出一行"None"。
分析：很明显的线段树区间求最值，区别：存在间断点特殊处理一下
/* 7 61 1 2 1 4 3 4 4 4 5 6 9 7 91 7 1 2 6 7 3 3 4 4 5 59 1 9 None 5 None */#include <cstdio> #include <cstring> #include <vector> #include <iostream> #include <algorithm> #define INF -0xfconst int maxn=1000005;using namespace std;struct node {int id;int price; };int segTree[maxn]; int a[maxn];void Build(int node, int b, int e) {if (b == e)segTree[node] = a[b];else{Build(2*node, b, (b+e)/2);Build(2*node+1, (b+e)/2+1, e);if (segTree[2 * node] >= segTree[2 * node + 1])segTree[node] = segTree[2 * node];elsesegTree[node] = segTree[2 * node + 1];} }int Query(int node,int b,int e,int left,int right) {if (b>=left && e<=right) return segTree[node];int m=(b+e)/2;int sum=0;if(left<=m)sum=max(sum,Query(node<<1,b,m,left,right));if(right>m)sum=max(sum,Query(node<<1|1,m+1,e,left,right));return sum; }int main() {int n,m;scanf("%d%d",&n,&m);int a1,a2;for (int i=1;i<=n;i++)a[i]=INF;for (int i=1;i<=n;i++){scanf("%d%d",&a1,&a2);if (a[a1] == INF) a[a1]=a2;else a[a1]=max(a[a1],a2);}Build(1,1,n);for (int i=1;i<=m;i++){scanf("%d%d",&a1,&a2);int ans=Query(1,1,n,a1,a2);if (ans == 0) printf("None\n");//特判else printf("%d\n",ans);}return 0; }
这篇关于题目1 : 打折机票(hihocoder 20挑战赛)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
