bupt oj1438解题报告

题目：服装节Submit: 622   Accepted:128Time Limit: 1000MS  Memory Limit: 65536KDescription
春 节来了~房教带着一帮912的ACMer去参加服装节，但是不幸的是，房教只有一块布。这块布长度为S(1<=S<=1,000,000)只 能做两件衣服。912一共有N位ACMer，编号为1..N；ACMer i的身高为Li（1<=Li<=1,000,000）。两位ACMer能共用这块布只有当他们的身高之和不大于这块布的长度。房教想知道有多 少对ACMer能够满足这块布。


Input
多组数据测试 每组数据第一行:两个整数：N和S，后面N行，第i+1行包含一个整数Li,N不大于20000
输入最后是两个0，0，表示输入结束。这组数据不做处理

Output
每组数据一行，一个整数表示有多少对ACMer能满足条件。注意两个ACMer的顺序没有关系。



Sample Input

4 6
3
5
2
1
0 0


Sample Output

4

分析：
   属于DP动态规划，使用双重循环属于O(n^2)复杂度，肯定超时。所以第一步排序（qsort是nlogn复杂度），然后从最大值到最小值开始判断，储存每个值符合条件的个数，下一个值可利用上一个值所储存的记录，避免重复计算。

代码：

#include<stdio.h>
#define M 20010
long cmp(const void *a, const void *b);
int main(int argc, char ** argv){

    long n,s,l[M]={0},cnt[M]={0},sum=0;
    int i,j,k;
    while( scanf ("%ld%ld", &n, &s),n != 0 && s != 0){
        for(i = 0;i < n; i++){
            scanf("%ld", &l[i] );
        }
        qsort(l, n, sizeof(long ), cmp);        
        for(i = n-1;i >0 ; i--){
            if( cnt[i+1] > 0) {
                cnt[i] = cnt[i] + cnt[i+1]-1;
                j=cnt[i+1] - 1;
            }    
            else
                j=cnt[i+1];
            for(; j < i; j++){
                if(l[i] + l[j] <= s) {
                    cnt[i]++;
                }
                else{
                    break;
                }
            }
        }

        for(i = 0;i < n; i++){
        //    printf("%ld ", cnt[i]);

            sum+=cnt[i];
            l[i]=0;
            cnt[i]=0;
        }
    
        printf("%ld\n", sum);
        sum=0;
    }
}
long cmp(const void *a, const void *b){
    
    return *(long *)a - *(long *)b ;


}