解题思路

这是一道求和为目标值的配对问题，主要思路如下：

  1. 问题分析：

    • n个茶杯，每杯含不同量的B型血红茶
    • 需要找出两杯茶的组合满足目标量
    • 如果有多种方案，按第一杯的量升序输出
    • 如果无解输出"NO"

  2. 解决方案：

    • 先将茶杯按血量排序
    • 使用双指针从两端向中间查找
    • 找到所有可能的组合并排序输出

  3. 双指针技巧：

    • 左指针从小到大遍历
    • 右指针从大到小遍历
    • 根据和与目标值的关系移动指针

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 读入数据
    int n;
    cin >> n;
    vector<int> cups(n);
    for(int i = 0; i < n; i++) {
        cin >> cups[i];
    }
    sort(cups.begin(), cups.end());  // 排序
    
    int target;
    cin >> target;
    
    // 双指针查找
    vector<pair<int,int>> result;
    int left = 0, right = n - 1;
    
    while(left < right) {
        int sum = cups[left] + cups[right];
        if(sum == target) {
            result.push_back({cups[left], cups[right]});
            left++;  // 继续寻找其他可能的组合
        } else if(sum > target) {
            right--;
        } else {
            left++;
        }
    }
    
    // 输出结果
    if(result.empty()) {
        cout << "NO" << endl;
    } else {
        for(const auto& p : result) {
            cout << p.first << " " << p.second << endl;
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读入数据
        int n = sc.nextInt();
        int[] cups = new int[n];
        for(int i = 0; i < n; i++) {
            cups[i] = sc.nextInt();
        }
        Arrays.sort(cups);  // 排序
        
        int target = sc.nextInt();
        
        // 双指针查找
        List<int[]> result = new ArrayList<>();
        int left = 0, right = n - 1;
        
        while(left < right) {
            int sum = cups[left] + cups[right];
            if(sum == target) {
                result.add(new int[]{cups[left], cups[right]});
                left++;
            } else if(sum > target) {
                right--;
            } else {
                left++;
            }
        }
        
        // 输出结果
        if(result.isEmpty()) {
            System.out.println("NO");
        } else {
            for(int[] pair : result) {
                System.out.println(pair[0] + " " + pair[1]);
            }
        }
    }
}

def find_pairs(cups, target):
    n = len(cups)
    cups.sort()  # 排序
    result = []
    
    # 双指针查找
    left, right = 0, n - 1
    while left < right:
        curr_sum = cups[left] + cups[right]
        if curr_sum == target:
            result.append((cups[left], cups[right]))
            left += 1
        elif curr_sum > target:
            right -= 1
        else:
            left += 1
    
    return result

def main():
    # 读入数据
    n = int(input())
    cups = list(map(int, input().split()))
    target = int(input())
    
    # 查找配对
    result = find_pairs(cups, target)
    
    # 输出结果
    if not result:
        print("NO")
    else:
        for pair in result:
            print(f"{pair[0]} {pair[1]}")

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：双指针
  • 时间复杂度： - 主要是排序的复杂度
  • 空间复杂度： - 存储结果的空间