Codeforces 525C - Ilya and Sticks (贪心)
题意
给出一堆数字,可以减一。问能组成的最大面积和。
思路
从大往小选,算一下。
一开始用队列模拟T了。
代码
#include <stack>
#include <stdio.h>
#include <list>
#include <cassert>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <cmath>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 1e6 + 10;
const int MOD = 9901;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int cases = 0;
typedef pair<int, int> pii;
int l[MAXN];
//适用于正负数,(int,long long,float,double)
template <class T>
bool Read(T &ret)
{
char c; int sgn; T bit=0.1;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&c!='.'&&(!isdigit(c))) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),isdigit(c)) ret=ret*10+(c-'0');
if(c==' '||c=='\n'){ ret*=sgn; return 1; }
while(c=getchar(),isdigit(c)) ret+=(c-'0')*bit,bit/=10;
ret*=sgn;
return 1;
}
int GetLong()
{
LL last = 0, ans = 0;
for (LL i = MAXN-1; i >= 2; i--)
{
int cnt = 0;
if (l[i])
{
if (l[i+1])
{
cnt++;
l[i]--;
}
cnt += l[i]/2;
if (cnt && last)
{
ans += last*i, cnt--;
last = 0;
}
l[i] = l[i] % 2;
ans += i*i*(cnt>>1);
if (cnt&1) last = i;
}
}
printf("%I64d\n", ans);
}
int main()
{
//ROP;
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int tmp;
Read(tmp);
l[tmp]++;
}
GetLong();
return 0;
}