A Kefa and First Steps
Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes ai money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence ai. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.
Help Kefa cope with this task!
Input
The first line contains integer n (1 ≤ n ≤ 105).
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Output
Print a single integer — the length of the maximum non-decreasing subsegment of sequence a.
Sample test(s)
input
6
2 2 1 3 4 1
output
3
input
3
2 2 9
output
3
Note
In the first test the maximum non-decreasing subsegment is the numbers from the third to the fifth one.
In the second test the maximum non-decreasing subsegment is the numbers from the first to the third one.
题目类型：线性DP
算法分析：dp[i]表示以第i个字符结尾的最长连续非递减子序列的长度，则边界为dp[1] = 1，状态转移方程为：若a[i-1] <= a[i]，则dp[i] = dp[i-1] + 1；否则dp[i] = 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 1666; int a[maxn], dp[maxn]; int main() { // CFF; int n; scanf ("%d", &n); for (int i = 1; i <= n; i++) scanf ("%d", &a[i]); fill (dp, dp + maxn, 1); for (int i = 2; i <= n; i++) { if (a[i] >= a[i-1]) dp[i] = dp[i-1] + 1; else dp[i] = 1; } int maxval = -INF; for (int i = 1; i <= n; i++) maxval = max (maxval, dp[i]); printf ("%d\n", maxval); return 0; } |
B Kefa and Company
Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.
Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn't want any friend to feel poor compared to somebody else in the company (Kefa doesn't count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!
Input
The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 105, ) — the number of Kefa's friends and the minimum difference between the amount of money in order to feel poor, respectively.
Next n lines contain the descriptions of Kefa's friends, the (i + 1)-th line contains the description of the i-th friend of type mi, si (0 ≤ mi, si ≤ 109) — the amount of money and the friendship factor, respectively.
Output
Print the maximum total friendship factir that can be reached.
Sample test(s)
input
4 5
75 5
0 100
150 20
75 1
output
100
input
5 100
0 7
11 32
99 10
46 8
87 54
output
111
Note
In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.
In the second sample test we can take all the friends.
题目类型：排序
算法分析：首先将输入的数据按照money从小到大排序，然后使用两个指针从头往后扫，即常说的“追逐法”
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6; struct node { LL v, w; }; bool operator < (const node aa, const node bb) {return aa.v < bb.v;} node aa[maxn]; int main() { // CFF; int n, d; scanf ("%d%d", &n, &d); for (int i = 1; i <= n; i++) scanf ("%I64d%I64d", &aa[i].v, &aa[i].w); sort (aa + 1, aa + 1 + n); LL maxval = -INF, tt = 0, ta = 1, tb = 1; for (; ta <= n; ta++) { while (tb <= n && aa[tb].v < aa[ta].v + d) { tt += aa[tb].w; tb++; } maxval = max (maxval, tt); tt -= aa[ta].w; } printf ("%I64d\n", maxval); return 0; } |
算法分析：也可以使用二分的方法来做，此时枚举所有的点a，然后查找a的val值+d的下界，最后通过维护的一个前缀和来将最大值更新，注意此时所有的节点之间的money都要满足差小于d！！！所以只能够计算[val, val + d)的值，不能够计算(val - d, val + d)的值！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define LL long long #define ULL unsigned long long #define DB(ccc) cout << #ccc << " = " << ccc << endl const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6; struct node { LL v, w; }; bool operator < (const node aa, const node bb) {return aa.v < bb.v;} node aa[maxn]; LL tt[maxn], sum[maxn]; int main() { // CFF; int n, d; scanf ("%d%d", &n, &d); for (int i = 0; i < n; i++) scanf ("%I64d%I64d", &aa[i].v, &aa[i].w); sort (aa, aa + n); tt[0] = aa[0].v; for (int i = 0; i < n; i++) { sum[i+1] = sum[i] + aa[i].w; tt[i] = aa[i].v; } // DB (sum[5]); LL res = -INF; for (int i = 0; i < n; i++) { int ta = lower_bound (tt, tt + n, tt[i] + d) - tt; // DB(ta); res = max (res, sum[ta] - sum[i]); } printf ("%I64d\n", res); return 0; } |