Des丨tiny丶柠凉

蓦然回首,前尘不堪流连,自卿离去,暗淡了这俗世繁华,只余孤影几度徘徊,独酌月下,对影成殇;

时间留不住记忆的海,不过是黯然神伤,默默着无奈。


stick解题报告

题目描述

LYK有很多木棍,具体的,总共有n根,且每根木棍都有一个长度。为了方便起见,我们可以用一个正整数ai表示第i根木棍的长度。
LYK有一把小刀,但这把小刀由于削木棍很不方便,对于一根木棍而言,它只能用这把小刀削掉恰好1的长度。
LYK觉得如果4根木棍头尾相连能恰好拼成长方形,说明这4根木棍是可以捆在一起卖钱的!具体的,如果这4根木棍的长度分别为a,b,c,d,如果满足a=b,c=d,说明恰好可以拼成长方形,且获得的钱为这4根木棍圈成的面积a*c。当然如果不能恰好拼成长方形,则卖不出去。
LYK想将这些木棍尽可能的4个一组捆在一起去卖钱,它想知道最多能获得多少钱。


输入格式

第一行一个数n,表示木棍的个数。
接下来一行n个数,第i个数ai表示第i根木棍的长度。


输出格式

一个数表示答案。


数据范围

对于30%的数据n=4。
对于50%的数据n<=20。
对于70%的数据n<=1000。
对于100%的数据1<=n<=100000,1<=ai<=1000000。

解题思路

长方形的两边等长,所以如果某个长度的木棍是长方形的两条边的话,这个长度的木棍必须有偶数根,如果当前长度的木棍有奇数根,就削去1的长度,
因为求面积,且数据范围ai<=1000000,所以会爆int…


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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
void read(int &x){
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x*10+c-48, c = getchar();
}
int cnt[1000020];
long long area;
int maxn,n,x;
bool flag;
int main(){
freopen("stick.in","r",stdin);
freopen("stick.out","w",stdout);
read(n);
for(int i = 1;i <= n;i++){
read(x);
cnt[x]++;
maxn = max(maxn,x);
}
for(int i = maxn;i >= 1;i--){
if((cnt[i]%2==1 && cnt[i]!=1) || (cnt[i]==1 && flag==0))
flag=1,cnt[i-1]++;
else flag = 0;
}
int last = 0;
for(int i = maxn;i >= 1;i--){
while(cnt[i] >= 2){
cnt[i] -= 2;
if(last != 0)
area += 1ll*last*i,last = 0;
else last = i;
}
}
printf("%lld",area);
return 0;
}

orz

最近的文章

alien解题报告

题目描述 给你一个R*C的地图,现在其中某些点已经有障碍物了,现在有一个大小为A+B的飞船需要降落在地图中的某个位置,要求飞船降落区域没有障碍物,请问有多少种降落区域选择的方案? 输入格式 第一行是四个整数,R C P Q接下来的P 行每行两个整数x,y表示(x,y)这个点为障碍物接下来的Q行每 …

于  前缀和 继续阅读
更早的文章

select解题报告

题目描述 LYK带着悲伤行走在黑暗里。寂穆的夜空没有星月的点缀,身旁的树木、房屋、万事万物连同你自己,都融于宇宙的虚无缥缈之中。黑暗,压抑、膨胀、严严实实包围整个世界,LYK害怕,彷徨,无奈。突然,眼前出现一扇窗,流漏出点点昏黄的灯光。LYK欣喜地奔去看,原来这里有n个数字,LYK深深地被它们吸引。 …

于  枚举 继续阅读