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