0928考试T2
题目大意：
给定K个数字序列，请将它们合并为一个，满足本来在同一序列中的两个数的相对位置不变。定义一个序列A的不和谐度为序列中使得A[i]>A[i+1]成立的i的总数，请输出一种合并方案，使得合并后的序列不和谐度最小。
考场上算错时间复杂度了，以为可以切了的，没想到拿了80。
我想的是贪心：假设已经填入(i - 1)个数，将要填第(i)个。首先找大于等于(a[i -1])的最小的一个数填入，如果找不到，找一个最小的比(a[i - 1])小的数填入。
举个例子：
合并前：
5 7 1 3
2 4 3 5
合并后：
2 4 5 7 1 3 3 5
正解的话不太好想，反正我没想到。（%%%同机房里想出的dalao）
我们只需要找合并前的序列的不和谐度最大的一个就好了。因为你肯定可以找到一个合适的位置插进去，把某一段变为一个单增的，这样是不会增加不和谐度的。（手画画就出来了）
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 2e5 + 5, K = 101, inf = 2147483647;
int k, ans, last;
int a, x, y, p, len, res;
int main() {
k = read();
for(int i = 1;i <= k; i++) {
len = read(); a = read(); last = res = 0;
x = read(), y = read(), p = read();
for(int j = 2;j <= len; j++) {
int tmp = (1ll * a * x % p + y) % p;
if(tmp < a) res ++;
a = tmp;
}
ans = max(ans, res);
}
printf("%d", ans);
fclose(stdin); fclose(stdout);
return 0;
}