Costume Party poj 3663 c++

超、凢脫俗 2022-08-10 16:35 117阅读 0赞

# Costume Party #

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 11252</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 4523</td> 
  </tr> 
 </tbody> 
</table>

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

题意：求n个数字中，有多少组的两个数字之和<=s;

思路：n的范围较小，用暴力枚举就可以，排序一下，从大到小，然后前面的满足后后面的一定满足，比较省时。

下面是代码：

#include<cstdio>
    #include<algorithm>
    using namespace std;
    int len[20200];
    
    int main()
    {
        int i,j,n,s,count;
        while(scanf("%d%d",&n,&s)!=EOF)
        {
            count=0;
            for(i=0;i<n;i++)
                 scanf("%d",&len[i]);
            sort(len,len+n);
            for(i=n-1;i>=0;i--)
            {
                if(len[i]<s)
                {
                   for(j=i-1;j>=0;j--)
                   {
                        if(len[i]+len[j]<=s)
                        {
                             count+=j+1;  // 只要是前面的加和满足，后面的加和一定满足； 
                             break;
                        }
                   }
                } 
            }  
            printf("%d\n",count);   
        }
        return 0;
    }