HDU 6047 Maximum Sequence （贪心）

HDU 6047 Maximum Sequence （贪心）

Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}: an+1…a2n. Just like always, there are some restrictions on an+1…a2n : for each number ai, you must choose a number bk from {bi}, and it must satisfy ai≤max(aj−j) (bk≤j

Input

The input contains no more than 20 test cases.For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.1≤n≤250000,n≤ai≤1500000,1≤bi≤n

Output

For each test case, print the answer on one line: max(∑2nn+1ai) modulo 109+7

Sample Input

48 11 8 53 1 4 2

Sample Output

27

题意

给出数列 A 和 B ，我们可以从 B 数列中取出一个编号来查找 A 数列中该编号及以后的位置中 Ai−i 的最大值并将其加入末尾，求 An+1..A2n

思路

题目很简单，但是题意好难懂。（可能是英语差的原因）

贪心思想，既然这样我们每次取 B 中当前编号最小的数字即可，因为这样才有机会让较大的数被加入到较前的位置，然后 Ai−i

具体可以用两个优先队列来实现。

AC 代码

#include #include #include #include #include #include#includeusing namespace std ;typedef __int64 LL;typedef pair P;const int mod = 1e9+7;int main(){ ios::sync_with_stdio(false); int n; while(cin>>n) { priority_queue

sk; priority_queue,greater >b; LL ans=0; for(int i=1; i<=n; i++) { LL x; cin>>x; sk.push(P(x-i,i)); } for(int i=1; i<=n; i++) { int x; cin>>x; b.push(x); } for(int ti=n+1; !b.empty(); ti++) { int i=b-(); b.pop(); while(sk-().second

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。