思路解析

把第 $i$ 个长方形放下时，只需在两种朝向里选一种：

• 令高度为 $x_i$、宽度为 $y_i$；
• 或令高度为 $y_i$、宽度为 $x_i$。

限制是高度 $\le m$。显然每个长方形彼此独立，总长度就是各自选择后的宽度之和，因此问题可分解为对每个 $i$ 局部做最优选择。

对单个长方形的最优宽度 $w_i$：

• 若 $\max(x_i,y_i)\le m$，两种朝向都合法。为了最小化占用长度，把较长的一边当高度，则宽度取较短一边： $w_i=\min(x_i,y_i).$
• 若 $\max(x_i,y_i)>m$，则只能把较短的一边当高度（因为较长一边会超过 $m$），于是宽度只能是较长一边： $w_i=\max(x_i,y_i).$

综上，统一写法：

答案为

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    if (!(cin >> n >> m)) return 0;

    long long ans = 0; // 使用64位整型，防止累加溢出
    for (int i = 0; i < n; ++i) {
        long long x, y;
        cin >> x >> y;
        long long mx = max(x, y);
        long long mn = min(x, y);
        // 若较长边也不超过m，则把较长边当高度，宽度取较短边
        // 否则只能用较短边当高度，宽度为较长边
        long long w = (mx <= m) ? mn : mx;
        ans += w;
    }
    cout << ans << "\n";
    return 0;
}

Python

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    ans = 0  # Python int 自动大数，这里直接累加即可
    for _ in range(n):
        x = int(next(it)); y = int(next(it))
        mx = x if x >= y else y
        mn = y if x >= y else x
        # 若较长边也不超过m，则选较短边作为宽度；否则宽度为较长边
        w = mn if mx <= m else mx
        ans += w

    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        long m = fs.nextLong();

        long ans = 0L; // 使用long，避免累加溢出
        for (int i = 0; i < n; i++) {
            long x = fs.nextLong();
            long y = fs.nextLong();
            long mx = Math.max(x, y);
            long mn = Math.min(x, y);
            // 若max(x, y) <= m，则宽度取min(x, y)；否则宽度取max(x, y)
            long w = (mx <= m) ? mn : mx;
            ans += w;
        }
        System.out.println(ans);
    }

    // 轻量高速输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && c <= ' ') {}
            if (c == -1) return null;
            do {
                sb.append((char) c);
                c = read();
            } while (c != -1 && c > ' ');
            return sb.toString();
        }

        int nextInt() throws IOException { return Integer.parseInt(next()); }
        long nextLong() throws IOException { return Long.parseLong(next()); }
    }
}

题目内容

小美有 $n$ 个长方形，第 $i$ 个长方形的两条边长分别为 $x_i,y_i$ ；

小美拥有一个仅包含第一象限的平面直角坐标系；

小美希望将这 $n$ 个长方形按顺序(可以旋转)放置在 $x$ 轴上，不允许重叠，并且每个长方形放置后的高度不超过 $m$ ，保证 $max(min(x_i,y_i))≦m$ ；

请问，在满足上述条件的前提下，小美最少需要占用 $x$ 轴的长度是多少?

输入描述

第一行输入两个整数 $n,m(1≦n≦2×10^5;1≦m≦10^9)$ ，分别表示长方形的个数和允许的最大高度；

接下来 $n$ 行，每行输入两个整数 $x_i,y_i(1≦x_i,y_i≦10^9)$ ，分别表示第 $i$ 个长方形的两条边长。

输出描述

输出一个整数，表示在每个长方形高是不好过 $m$ 的情况下，所需占用的最短 $x$ 轴长度。

样例1

输入

3 4
1 2
2 5
4 2

输出

8

说明

• 第 $1$ 个长方形可用高度较小的一条边放置，高度 $2≤ 4$ ，占用长度 $min(1,2)=1$ ；

• 第 $2$ 个长方形仅能以高度 $2$ 放置，占用长度 $5$ ；

• 第 $3$ 个长方形可用较小的一条边放置，占用长度 $min(4,2)=2$ ；

因此总长度为 $1+5+2=8$ 。