710
POJ-3663-Costume Party
Costume Party
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 11237 Accepted: 4512
Description
It's Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The costume fits precisely two cows with a length of S (1 ≤ S ≤ 1,000,000). FJ has N cows (2 ≤ N ≤ 20,000) conveniently numbered 1..N; cow i has length Li (1 ≤ Li ≤ 1,000,000). Two cows can fit into the costume if the sum of their lengths is no greater than the length of the costume. FJ wants to know how many pairs of two distinct cows will fit into the costume.
Input
* Line 1: Two space-separated integers: N and S
* Lines 2..N+1: Line i+1 contains a single integer: Li
Output
* Line 1: A single integer representing the number of pairs of cows FJ can choose. Note that the order of the two cows does not matter.
Sample Input
4 6
3
5
2
1
Sample Output
4
Source
USACO 2008 January Bronze
前兩天比賽的題，腦子抽筋沒優化超時了，今天看看，真簡單啊，罪過罪過～～～
題意：有一組數組N，要求這N個數兩兩組合能拚湊出多少對和（Ni+Nj）小於或等於M的組合
AC代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 20020
int a[MAXN];
int main()
{
int i,j,n,m,sum,temp;
while(scanf("%d %d",&n,&m)!=EOF)
{
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
temp=n;
sum=0;
for(i=0;i<temp;i++)
for(j=i+1;j<temp;j++)
{
if(a[i]+a[j]<=m)
{
sum++;
}
else
{
temp=j;//優化,後麵的怎麼加都大於長度，就沒有必要納入每次的計算了
break;
}
}
printf("%d",sum);
}
return 0;
}
最後更新：2017-04-03 05:39:38