1 条题解

  • 0
    @ 2024-8-2 16:19:45

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    
    int a[60]; // 第i个正方形的大小
    int p[60]; // 第i个正方形角的落点位置
    int l[60]; // 第i个正方形左侧所有正方形最大的右端点
    int r[60]; // 第i个正方形右侧所有正方形最小的左端点
    
    int main() {
        int m;
        cin >> m;
    
        for (int i = 1; i <= m; i++) {
            cin >> a[i];
            a[i] *= 2;
    
            for (int j = 1; j < i; j++)
                p[i] = max(p[i], p[j] + min(a[j], a[i]));
        }
    
        for (int i = 1; i <= m; i++) {
            l[i] = p[i] - a[i] / 2;
            r[i] = p[i] + a[i] / 2;
    
            for (int j = 1; j < i; j++) {
                if (a[i] < a[j]) {
                    l[i] = max(l[i], p[j] + a[j] / 2);
                }
            }
    
            for (int j = i + 1; j <= m; j++) {
                if (a[i] < a[j]) {
                    r[i] = min(r[i], p[j] - a[j] / 2);
                }
            }
    
            // l < r 说明没有交集,则未被覆盖
            if (l[i] < r[i]) {
                cout << i << " ";
            }
        }
    
        return 0;
    }
    
    
    • 1

    信息

    ID
    1020
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者