P4889 kls与flag

一堆杆子， 每个有特定高度 \(a_{i}\) ， 现想把杆子弄倒， 可以在一维内往左弄倒和往右弄倒， 求最大优秀对数， 定义优秀对数为两杆倒后顶点重合

Solution

话说见证了这题从蓝变绿又变蓝啊

首先杆子倒下无非两种状态， 向左或向右

我们维护倒下后处在的坐标即可

显然每个杆子有两个坐标， 可以用桶维护

但是数组无法开最大高度 + 所处位置那么大

所以用 \(map\) 当桶即可

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#include<map>

#define LL long long

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const LL maxn = 400019;

LL num, m, cnt;

map<LL, LL>ton;

int main(){

	num = RD(), m = RD();

	for(LL i = 1;i <= num;i++){

		LL a = RD();

		cnt += ton[i - a];

		cnt += ton[i + a];

		ton[i - a]++, ton[i + a]++;

		}

	printf("%lld\n", cnt);

	return 0;

	}