class sig clas linker freopen memset seq deb
题意:给定一个序列,让你构造出一个序列,满足条件,且最大。条件是 选取一个 ai <= max{a[b[j], j]-j}
析:贪心,贪心策略就是先尽量产生大的,所以就是对于 B 序列尽量从头开始,由于数据比较大,采用桶排序,然后维护一个单调队列,使得最头上最大。
代码如下:
- #pragma comment(linker, "/STACK:1024000000,1024000000")#include < cstdio > #include < string > #include < cstdlib > #include < cmath > #include < iostream > #include < cstring > #include < set > #include < queue > #include < algorithm > #include < vector > #include < map > #include < cctype > #include < cmath > #include < stack > #include < sstream > #include < list > #define debug() puts("++++");#define gcd(a, b) __gcd(a, b)#define lson l,
- m,
- rt << 1#define rson m + 1,
- r,
- rt << 1 | 1#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout) using namespace std;
- typedef long long LL;
- typedef unsigned long long ULL;
- typedef pair < int,
- int > P;
- const int INF = 0x3f3f3f3f;
- const double inf = 0x3f3f3f3f3f3f;
- const double PI = acos( - 1.0);
- const double eps = 1e-8;
- const int maxn = 250000 + 10;
- const LL mod = 1e9 + 7;
- const int dr[] = { - 1,
- 0,
- 1,
- 0
- };
- const int dc[] = {
- 0,
- 1,
- 0,
- -1
- };
- const char * de[] = {
- "0000",
- "0001",
- "0010",
- "0011",
- "0100",
- "0101",
- "0110",
- "0111",
- "1000",
- "1001",
- "1010",
- "1011",
- "1100",
- "1101",
- "1110",
- "1111"
- };
- int n,
- m;
- const int mon[] = {
- 0,
- 31,
- 28,
- 31,
- 30,
- 31,
- 30,
- 31,
- 31,
- 30,
- 31,
- 30,
- 31
- };
- const int monn[] = {
- 0,
- 31,
- 29,
- 31,
- 30,
- 31,
- 30,
- 31,
- 31,
- 30,
- 31,
- 30,
- 31
- };
- inline bool is_in(int r, int c) {
- return r > 0 && r <= n && c > 0 && c <= m;
- }
- int num[maxn];
- int a[maxn << 1];
- int q[maxn << 1];
- int main() {
- while (scanf("%d", &n) == 1) {
- memset(num, 0, sizeof num);
- for (int i = 1; i <= n; ++i) scanf("%d", a + i);
- for (int i = 0; i < n; ++i) {
- scanf("%d", &m); ++num[m];
- }
- int fro = 0,
- rear = 0;
- q[++rear] = 1;
- for (int i = 2; i <= n; ++i) {
- while (rear > fro && a[i] - i >= a[q[rear]] - q[rear])--rear;
- q[++rear] = i;
- }
- int cnt = 1;
- for (int i = n + 1; i <= n + n; ++i) {
- while (!num[cnt])++cnt; --num[cnt];
- while (q[fro + 1] < cnt)++fro;
- a[i] = a[q[fro + 1]] - q[fro + 1];
- while (rear > fro && a[i] - i >= a[q[rear]] - q[rear])--rear;
- q[++rear] = i;
- }
- int ans = 0;
- for (int i = n + 1; i <= n + n; ++i) ans = (ans + a[i]) % mod;
- printf("%d\n", ans);
- }
- return 0;
- }
HDU 6047 Maximum Sequence (贪心 + 单调队列)
来源: http://www.bubuko.com/infodetail-2231153.html