多校二 1003Maximum Sequence 模拟
Maximum Sequence
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total
Submission(s): 1887 Accepted Submission(s): 671
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<i}, and any bk
can’t be chosen more than once. Apparently, there are a great many
possibilities, so you are required to find max{∑2nn+1ai
} modulo 109
+7 .
Now Steph finds it too hard to solve the problem, please help
him.
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≤a_i≤1500000, 1≤b_i≤n.
max{∑2nn+1ai
} modulo 109
+7。
8 11 8 5
3 1 4 2
For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;
a: 8 11 8 5
a[i]-i: 7 9 5 1
b:3 1 4 2
先将b排序得到 b: 1 2 3 4
那么取第一个b[0]=1 那么取到9
a:8 11 8 5 9
a[i]-i: 7 9 5 1 4
b[1]=2 还是取到 9
a: 8 11 8 5 9 9
a[i]-i: 7 9 5 1 4 3
后面继续这样取最终得到的是
a: 8 11 8 5 9 9 5 4 多出来的就是 27
那么从模拟的这个过程可以发现,只要记录当前位置到n中间的最大值 和更新出来的数中的最大值
进行比较取最大的那个,就是答案啦~
代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 300009
#define mod 1000000007
long long a[N], b[N], maxa[N];
int main()
{
int n;
while(scanf("%d", & n) != EOF)
{
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(maxa, 0, sizeof(maxa));
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
a[i] = a[i] - i;
}
for(int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
sort(b, b+n+1);
for(int i = n ; i >= 1; i--)
{
maxa[i] = max(maxa[i+1], a[i]);
}
long long ans = 0;
ans += maxa[b[1]];
ans %= mod;
long long t = maxa[b[1]] - n - 1;
for(int i = 2; i <= n; i++)
{
maxa[b[i]] = max(maxa[b[i]], t);
ans += maxa[b[i]];
ans %= mod;
t = max(t, maxa[b[i]] - n - i);
}
printf("%lld\n", ans);
}
}
最新文章
- JQuery Sizzle引擎源代码分析
- php模拟http请求的方法
- 通俗易懂的 JSon解析处理
- java匿名类和匿名对象及this的其他用法
- 个人作业-Week2:案例分析
- J2EE学习笔记-第二章(Web应用初步)
- url rewrite优化url的可读性
- Progress Control with Text
- Spring常用的接口和类(三)
- 20145211 《Java程序设计》第1周学习总结——小荷才露尖尖角
- confirm的用法
- 工作流引擎Activiti使用总结
- 【LeetCode】Agorithms 题集(一)
- jdbc mysql - Column count doesn&#39;t match value count at row 1.
- 高仿QQ即时聊天软件开发系列之一开端
- Android 颜色大全 (colors.xml )
- 查看linux信息
- UVa 1600 Patrol Robot (习题 6-5)
- CentOS 7 PHP-redis扩展安装,浏览器不显示数据及redis无法储存数据常见问题解决办法
- 使用Keras对交通标志进行分类
热门文章
- CheckStyle报错的常见问题及解决方式
- Java入门 - 高级教程 - 03.泛型
- spring cloud的配置
- jquery的版本 纵多 , 各个版本的插件的融合 ,
- ubutun安装停留在界面
- Qt Installer Framework翻译(7-5)
- ImportError: Failed to import pydot. You must install pydot and graphviz for `pydotprint` to work.
- Nginx-负载均衡实现解读
- http轮询,长轮询
- Future、Callback、Promise