DAY2T1

贪心贪心贪心！！！

题目
木棍(stick)
Time Limit:1000ms Memory Limit:128MB

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

输入格式(stick.in)
第一行一个数n，表示木棍的个数。
接下来一行n个数，第i个数ai表示第i根木棍的长度。

输出格式(stick.out)
一个数表示答案。

输入样例
12
2 3 3 4 5 5 5 5 7 9 11 13

输出样例
31

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

很显然，如果某个木棒长度的数量是奇数，那么肯定是把一根木棒减1最优
因为留着没用，削了还可能出一个新的对棒
代码如下

#include 
#include 
using namespace std;
long long sum1[1000000]; 
long long sum2[1000000];
long long ans;
int main()
{int n;int maxm=0;scanf("%d",&n);for(int i=1,x;i<=n;i++)scanf("%d",&x),sum1[x]++,maxm=max(maxm,x);for(int j=maxm;j>=1;j--){if((sum1[j]+sum2[j])%2!=0)if(sum1[j]!=0) sum1[j]--,sum2[j-1]++;sum1[j]=sum1[j]+sum2[j];}long long c=0;for(long long j=maxm;j>=1;j--){if(sum1[j]%2==0&&sum1[j]){while(sum1[j]>=2){if(c!=0) ans+=j*c,c=0;else     c=j;sum1[j]-=2;}}   }printf("%lld",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！