题解：Costume Party（P3663）

一、题目分析

本题要求计算有多少对不同的奶牛可以穿上同一套服装，条件是两头奶牛的身长之和不超过服装长度S。关键信息：

• 奶牛数量N（2≤N≤20,000），服装长度S（1≤S≤1,000,000）
• 每头奶牛身长Li（1≤Li≤1,000,000），求满足Li+Lj≤S的(i,j)对数（i<j）

二、解题思路

1. 排序优化：
   先将奶牛身长数组排序，便于后续高效查找。

2. 双指针法：
   固定一头奶牛i，找到所有j>i且满足Li+Lj≤S的奶牛j。由于数组已排序，可通过移动右指针快速确定符合条件的j范围。

3. 复杂度优化：
   暴力枚举每对奶牛的时间复杂度为O(N²)，排序后使用双指针可优化至O(N log N + N)。

三、代码解析

/* POJ3663 Costume Party */

#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 20000;
int a[N];

int main()
{
    int n, s;
    while (~scanf("%d%d", &n, &s)) {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);

        sort(a, a + n);  // 排序奶牛身长

        int end = n, cnt = 0;
        for (int i = 0; i < end; i++) {
            for (int j = i + 1; j < end; j++) {
                if (a[i] + a[j] <= s)
                    cnt++;
                else {
                    end = j;  // 后续j更大，无需继续搜索
                    break;
                }
            }
        }

        printf("%d\n", cnt);
    }

    return 0;
}

四、关键步骤解析

1. 排序数组
   使用$sort(a, a + n)$对奶牛身长排序，为后续双指针优化做准备。

2. 双指针枚举

   • 外层循环固定奶牛i（i从0到n-1）
   • 内层循环从j=i+1开始，找到最大的j使得a[i]+a[j]≤S
   • 当a[i]+a[j]>S时，由于数组有序，后续j更大，直接break并更新end=j，减少重复判断

3. 计数逻辑
   每找到一对满足条件的(i,j)，计数器cnt加1，最终输出cnt。

五、示例解析

以输入为例：

4 6
3 5 2 1

1. 排序后数组：$[1, 2, 3, 5]$

2. 枚举过程：

   • i=0（a[i]=1）：
     j=1:1+2=3≤6→cnt=1
     j=2:1+3=4≤6→cnt=2
     j=3:1+5=6≤6→cnt=3
     j=4超出范围，结束
   • i=1（a[i]=2）：
     j=2:2+3=5≤6→cnt=4
     j=3:2+5=7>6→break，end=3
   • i=2（a[i]=3）：
     j=3:3+5=8>6→break，end=3
   • i=3：无j>i

3. 结果：共4对，输出4。

六、优化分析

1. 原代码优化空间
   原代码的时间复杂度为O(N²)，当N=20,000时会超时。更优解法是使用双指针法：

#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 20000;
int a[N];

int main()
{
    int n, s;
    while (~scanf("%d%d", &n, &s)) {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);

        sort(a, a + n);

        int cnt = 0;
        for (int i = 0, j = n - 1; i < j;) {
            if (a[i] + a[j] <= s) {
                cnt += j - i;  // i与i+1~j都可配对
                i++;
            } else {
                j--;
            }
        }

        printf("%d\n", cnt);
    }

    return 0;
}

2. 双指针法原理
   • i从左向右，j从右向左
   • 若a[i]+a[j]≤s，说明a[i]与a[i+1]~a[j]都可配对，计数j-i，i右移
   • 若a[i]+a[j]>s，j左移减少和

七、复杂度分析

• 排序复杂度：O(N log N)
• 双指针枚举：O(N)
• 总复杂度：O(N log N)，可处理N=20,000的数据。

八、注意事项

1. 数据范围：
   S和Li可达10⁶，需用int存储，但不会溢出。

2. 配对去重：
   i<j保证每对仅计数一次，避免重复。

3. 边界条件：
   当N=2时，直接判断两数之和是否≤S。

九、扩展思考

1. 三维扩展：
   若求三元组(i,j,k)满足Li+Lj+Lk≤S，可固定i,j，用二分查找k的范围。

2. 负数处理：
   若Li可为负数，排序后双指针法仍适用，但需调整移动逻辑。