2064. Caterpillars
Time limit: 3.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Young gardener didn’t visit his garden for a long time, and now it’s not very pleasant there: ncaterpillars have appeared on the ground.
Kirill decided to use this opportunity to have some fun and organized a competition — "caterpillar crawl-race."
At Kirill’s command all caterpillars start crawling from the ground to the top of a tree. But they get tired pretty fast. After crawling ti cm i-th caterpillar needs to rest for ti minutes. During that time it slides down a bit. Crawling speed of a caterpillar is 1 cm/minute, sliding speed — also 1 cm/minute.
Kirill is very much interested to find out how high on the tree is the leading caterpillar at different moments in time.
Input
First line contains one integer n — the number of caterpillars (1 ≤ n ≤ 106).
Second line contains n integers ti — characteristics of caterpillars (1 ≤ ti ≤ 109).
In the third line there is a number q — number of moments in time, which Kirill finds interesting (1 ≤ q ≤ 106).
Remaining q lines contain one query from Kirill each. A query is described by xi — number of minutes since the start of the competition (1 ≤ xi ≤ 106).
Output
For every query print in a separate line one integer, that describes how high is the highest caterpillar at the given moment of time.
Sample
| input | output |
|---|---|
4 |
1 |
Problem Author: Nikita Sivukhin (prepared by Alexey Danilyuk, Nikita Sivukhin)
Problem Source: Ural Regional School Programming Contest 2015
Problem Source: Ural Regional School Programming Contest 2015
Tags: none (hide tags for unsolved problems)
Difficulty: 559
题意：有n只蜗牛，对于第i只蜗牛，有性质ti，这只蜗牛往上爬ti秒，有下降ti秒，上升下降速度都是1cm/s，问第x秒爬得最高的蜗牛多高。
分析：首先画出蜗牛们的高度的函数，就可以看到它们是周期的类似三角形的函数。
如果我们只关注最高点，那么第x秒的答案是
max{a[i] - abs(x - i)}
其中a[i]表示在第i秒这个点的最高点最大是多少。
把那个abs拆开，分成x<i,x>i讨论
发现当x>i时
a[i]+i - x
当x<i时
a[i]-i + x
所以用是不是有点像单调队列？
其实我们只用记录最大值即可。
/**
Create By yzx - stupidboy
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mk make_pair inline int getInt()
{
int ret = ;
char ch = ' ';
bool flag = ;
while(!(ch >= '' && ch <= ''))
{
if(ch == '-') flag ^= ;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
ret = ret * + ch - '';
ch = getchar();
}
return flag ? -ret : ret;
} const int N = ;
int n, m, cnt[N];
int ans[N]; inline void input()
{
for(cin >> n; n--; )
{
int x, t;
cin >> x;
for(t = x; t < N; t += * x)
cnt[t] = max(cnt[t], x);
cnt[N - ] = max(cnt[N - ], x - (t - (N - )));
}
cin >> m;
} inline void solve()
{
for(int i = , now = -INF; i < N; i++)
{
now = max(now, cnt[i] + i);
ans[i] = max(ans[i], now - i);
}
for(int i = N - , now = -INF; i > ; i--)
{
now = max(now, cnt[i] - i);
ans[i] = max(ans[i], now + i);
} while(m--)
{
int x;
cin >> x;
cout << ans[x] << "\n";
}
} int main()
{
ios::sync_with_stdio();
input();
solve();
return ;
}