首页 > 代码库 > POJ 2231 贪心吗?怎么感觉像是数学。。。。

POJ 2231 贪心吗?怎么感觉像是数学。。。。

过了两次用了两种不同方法,其实也差不多,如果真的暴力去求得话铁定超时,(好像优化减去一些不可能的情况也能过,但是我没尝试)所以找一下规律咯,没学过算法的渣只能靠思维做题了。。。

#include<stdio.h>int a[10009];int main(){    int n,m,t,i,j;    long long sum;    while(scanf("%d",&n)!=EOF)    {   sum=0;        for(i=1;i<=n;i++)        scanf("%d",&a[i]);        for(i=1;i<n;i++)        for(j=i+1;j<=n;j++)        {        if(a[i]<a[j]){ t=a[i];a[i]=a[j];a[j]=t;}先排序保证前面大后面小        }        for(i=1;i<=n;i++)        {        sum=sum+a[i]*(long long)(n-i*2+1);//因为找到规律15 14 13 12…………家的有15加了15-1次14加了15-2次……减得有15剪了0次 14 1次 13 2次…………就是a[i]加了n-i次减了i-1次,规律就是每一项的总值是a[i]*(n-i-(i-1)) 注意这个值会溢出前面需要加上longlong       }        printf("%lld\n",sum*2);        }}

 其实这个算法我是没打算过的,但是加了一句 sum=sum+a[i]*(long long)(n-i*2+1);中的longlong就过了,好吧,在计算的时候就溢出了,怪不得一直WA

然后更优化的算法是这个

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;

int a[10009];

int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,j;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}

sort(&a[0],&a[n]);

long long all=0;
for(i=1;i<n;i++)
{
all+=(long long)i*(n-i)*(a[i]-a[i-1]);
}
all=all*2;
printf("%lld\n",all);
}
}
这个规律也是需要自己找
4
1 3 5 8
(3-1)*(1*3)+(5-3)*(2*2)+(8-5)*(3*1)