#P2022. 魅力花园(park)
魅力花园(park)
【问题描述】
在城市里会有很多花园,我们如何判断某一个花园是不是魅力花园呢?不同的人有不同的要求,而且花园对于不同的人的要求的敏感程度不同。比如市长的要求要比市民的要求有用的多,城管的要求又高于市长的要求。花园的园长很为难。他必须让尽可能多的人都感到满意。
假设有𝑛个群体对花园提出了𝑛个要求,每个群体的要求不同,园长根据要求被提出的时间先后和要求的价值大小进行选择性的满足。园长只会对时间早的和价值高的要求进行满足。例如两个要求𝐴和𝐵的提出时间分别是𝑎, 𝑏(𝑎<𝑏),价值分别是𝑎′,𝑏′(𝑎′>𝑏′),那么他们可以同时被满足。
园长为了打造魅力花园,当然希望满足尽可能多的不同群体的要求。他想让你帮他设计一个规划,计算出最多能满足多少个群体的要求。
【输入格式】
第一行一个𝑛,表示有𝑛个群体;
第二行𝑛个整数,𝑛个群体的问题的时间由早到晚排序后的标号顺序;
第三行𝑛个整数,𝑛个群体的问题的价值从大到小排序后的标号顺序;
【输出格式】
一个数表示最多能满足的要求数;
【输入样例】
5
1 3 4 5 6
6 5 3 4 1
【输出样例】
2
【数据范围】
30%的数据:1≤𝑛≤1000;
100%的数据:1≤𝑛≤100000;
相关
在下列比赛中: