用 hash 做
| Accepted |
1280 |
0MS |
292K |
1236B |
G++ |
//典型的hash: 用數組下標表示兩兩相加所得到的和，開辟一個滿足題意的大小的數組 sum，
//這樣下標由大到小輸出m個就可以
#include <iostream>
#include <string>
using namespace std;
int main ()
{
int a[3001];
int sum[10001];
int n, m;
while ( scanf ("%d %d", &n, &m) != EOF )
{
memset ( a, 0, sizeof (a) );
memset ( sum, 0, sizeof (sum) );
for ( int i = 0; i < n; i ++ )
{
scanf ("%d", &a[i]);
}
int temp;
for ( int i = 0; i < n; i ++ )
{
for ( int j = i + 1; j < n; j++ )
{
temp = a[i] + a[j];
sum[temp] ++;
}
}
int count = 0; //輸出前 m 個數
for ( int i = 10001; i >= 0 ; i -- )
{
if ( sum[i] )
{
for (int j = 0; j < sum[i]; j ++)
{
count ++;
count == 1 ? printf ("%d", i) : printf (" %d", i);
if ( count == m )
break;
}
}
if ( count == m )
break;
}
printf ("\n");
}
// system ("pause");
return 0;
}
所以改用sort排序后再輸出
| Accepted |
1280 |
843MS |
17888K |
1304B |
G++ |
//典型的hash: 用數組下標表示兩兩相加所得到的和，開辟一個滿足題意的大小的數組 sum，
//這樣下標由大到小輸出m個就可以
#include <iostream>
#include <string>
using namespace std;
int sum[4500000]; //開全局數組才能過
bool cmp ( const int &a, const int &b )
{
return a > b;
}
int main ()
{
int a[3001];
int n, m;
while ( scanf ("%d %d", &n, &m) != EOF )
{
memset ( a, 0, sizeof (a) );
memset ( sum, 0, sizeof (sum) );
//輸入處理
for ( int i = 0; i < n; i ++ )
{
scanf ("%d", &a[i]);
}
//兩數求和
//int k = n * ( n - 1 ) / 2;
int temp = 0;
for ( int i = 0; i < n; i ++ )
{
for ( int j = i + 1; j < n; j ++ )
{
sum[temp ++] = a[i] + a[j];
}
}
sort ( sum, sum + temp, cmp );
int count = 0;
for ( int i = 0; i< temp; i ++ )
{
count ++;
count == 1 ? printf ("%d", sum[i]): printf (" %d",sum[i]);
if ( count == m )
break;
}
printf ("\n");
}
// system ("pause");
return 0;
}
posted on 2010-08-28 16:43
雪黛依夢 閱讀(447)
評論(0) 編輯 收藏 引用 所屬分類:
哈希法 、
排序題