P4613 长方形比大小（基础）

解题思路

这道题的关键不只是排序，还有一个容易踩的"坑"。我们分四步来讲。

第一步，明确排序规则。 长方形按"谁大谁优先"排序：面积大的排前面；面积一样大时，周长长的排前面。面积 = 长 × 宽，周长 = 2 ×（长 + 宽）。我们用结构体 Rect 保存每个长方形的序号、面积和周长。

第二步，发现一个大坑：int 溢出。 题目里的长和宽可以大到几十万，两个数相乘得到的面积会远远超过 int 类型能表示的约 21 亿，发生"溢出"。这就好比钟表的指针转了一圈又回到原点，溢出的数值会变成意想不到的"乱码"。比如长 50000、宽 50000，真实面积是 25 亿，超过 int 上限，溢出后在 int 里存的竟然是 -1794967296 这个负数！本题的标程就是用这种"溢出之后的值"来排序的，如果老老实实用 long long 算出真实面积，反而会和标准答案对不上。所以我们的代码必须复现 int 溢出的行为。

第三步，用无符号运算模拟溢出。 代码里用 (unsigned)length * (unsigned)width 计算面积，用 ((unsigned)length + (unsigned)width) * 2u 计算周长。无符号乘法发生进位时只保留低 32 位，恰好模拟了 int 溢出后的截断值，结果与标程完全一致。

第四步，排序并输出。 用 sort() 加比较函数排序：先比面积，面积相同比周长。题目保证不会出现面积、周长都相同的两个长方形，所以不会并列。排好后按顺序输出每个长方形的原始序号（1 到 n），每行一个。

**回顾总结。**这道题表面是排序，真正的考点是 int 溢出。先意识到"标程用溢出的面积排序"，再用无符号运算精确复现 32 位截断，最后套用排序模板输出序号。搞清楚溢出前后的数值变化，才能和标准答案保持一致。

参考代码

// 长方形比大小：按面积降序、周长降序排列，输出原序号
// 注意：本题数据生成的标程用 int 计算面积，溢出后按 32 位截断值排序，需复现该行为
#include <iostream>
#include <algorithm>
using namespace std;

// 保存一个长方形的信息
struct Rect {
    int id;         // 序号（1~n，按输入顺序）
    int area;       // 面积（int 溢出后的 32 位截断值）
    int perimeter;  // 周长（int 溢出后的 32 位截断值）
};

// 自定义比较函数：面积大的靠前，面积相同则周长长的靠前
bool cmp(const Rect &a, const Rect &b) {
    if (a.area != b.area) return a.area > b.area;
    return a.perimeter > b.perimeter;
}

int main() {
    int n;
    Rect rects[105];
    cin >> n;
    for (int i = 0; i < n; i++) {
        int length, width;
        cin >> length >> width;
        rects[i].id = i + 1;
        // 用无符号乘/加模拟 int 溢出的 32 位截断（结果与标程一致）
        rects[i].area = (int)((unsigned)length * (unsigned)width);
        rects[i].perimeter = (int)(((unsigned)length + (unsigned)width) * 2u);
    }
    sort(rects, rects + n, cmp);   // 按"谁大谁优先"排序
    for (int i = 0; i < n; i++) {
        cout << rects[i].id << endl;          // 输出排序后的序号
    }
    return 0;
}

复杂度分析

排序使用 sort()，时间复杂度是 O(n log n)，n 是长方形个数（小于 100）。每个结构体存了三个整数，空间复杂度是 O(n)。计算面积和周长都是 O(1) 的，整个程序运行时间可以忽略不计。