这道题本身就是一个**“建模 + 贪心统计”的经典题型

一、题意重新梳理（把问题“翻译成人话”）

  • 教室是一个 n 行 m 列 的网格同学坐在 (i, j)。
  • 可以修：k 条 横向通道（在第 ai 行和 ai+1 行之间）l 条 纵向通道（在第 bi 列和 bi+1 列之间）
  • 有 d 对“经常交头接耳”的同学每一对 一定是相邻的（上下 or 左右）
  • 如果一条通道正好修在这两个人之间，就能把这对人隔开

👉 目标是：选择 k 条横通道 + l 条纵通道，使得“被隔开的交头接耳对”尽可能多（等价于：没被隔开的尽量少）

题目保证：最优方案唯一

二、核心建模

1️⃣ 每一对交头接耳，贡献给“某一条通道”

  • 如果两个人 左右相邻：(x, y) 和 (x, y+1)那么只要在 第 y 列和 y+1 列之间修纵向通道，就能隔开👉 这对人 只和这一条纵向通道有关
  • 如果两个人 上下相邻：(x, y) 和 (x+1, y)那么只要在 第 x 行和 x+1 行之间修横向通道，就能隔开👉 这对人 只和这一条横向通道有关

⚠️ 非常关键的一点：每一对交头接耳，只能被“唯一的一条通道”隔开

2️⃣ 问题转化成了什么？

  • 对每一条“行间通道”，统计：有多少对人是靠这条通道才能被隔开的
  • 对每一条“列间通道”，统计：有多少对人是靠这条通道才能被隔开的

然后：

从所有行间通道中，选出 k 条“贡献最大的”从所有列间通道中，选出 l 条“贡献最大的”

这就是一个独立的贪心选择问题。

三、数据结构设计

struct jo
{
    int num , z ; 
};

含义：

  • num： 这条通道能隔开的“交头接耳对”的数量
  • z： 通道编号（第几行 / 第几列）

两个数组分别统计：

vector<jo> a1(n + 1); // 行间通道（横向）
vector<jo> a2(m + 1); // 列间通道（纵向）

初始化编号：

for(int i = 1 ; i <= n ; i++) a1[i].z = i;
for(int i = 1 ; i <= m ; i++) a2[i].z = i;

四、统计每条通道的“价值”

while(d--)
{
    int x1 , y1 , x2 , y2 ;  
    cin >> x1 >> y1 >> x2 >> y2 ; 

    if(x1 == x2)
    {
        // 左右相邻 → 纵向通道
        a2[min(y1 , y2)].num++;
    }
    else if(y1 == y2)
    {
        // 上下相邻 → 横向通道
        a1[min(x1 , x2)].num++;
    }
}

解释得非常重要：

  • min(y1, y2) 表示“第 y 列和 y+1 列之间”的那条纵向通道
  • min(x1, x2) 表示“第 x 行和 x+1 行之间”的那条横向通道

👉 每对人 只给一条通道 +1

五、贪心选择（题目保证最优唯一）

1️⃣ 按贡献从大到小排序

sort(all(a1), cmp);
sort(all(a2), cmp);

cmp：

bool cmp(const jo& a , const jo& b)
{
    return a.num > b.num;
}

2️⃣ 取前 k / l 条

for(int i = 0 ; i < k ; i++) ans1.push_back(a1[i]);
for(int i = 0 ; i < l ; i++) ans2.push_back(a2[i]);

3️⃣ 按编号升序输出（题目格式要求）

sort(all(ans1), cmp1);
sort(all(ans2), cmp1);


bool cmp1(const jo & a , const jo & b)
{
    return a.z < b.z;
}

六、输出部分

for(int i = 0 ; i < k ; i++)
{
    cout << ans1[i].z;
    if(i != k -1) cout << " ";
}
cout << endl;

for(int i = 0 ; i < l ; i++)
{
    cout << ans2[i].z;
    if(i != l - 1) cout << " ";
}

严格符合题目输出格式：

  • 第一行：横向通道行号
  • 第二行：纵向通道列号

七、复杂度分析

  • 统计：O(d)
  • 排序：行：O(n log n)列：O(m log m)
  • n, m ≤ 1000，完全没压力

总代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define all(a) a.begin(), a.end()
struct jo
{
    int num , z ; 
};
bool cmp(const jo& a , const jo& b)
{
    return a.num > b.num;
}
bool cmp1(const jo & a , const jo & b)
{
    return a.z < b.z;
}
void work() 
{
    int n , m , k , l  , d ; cin >> n >> m >> k >> l >> d ; 
    vector<jo>a1(n + 1 , {0 , 0});
    vector<jo>a2(m + 1 , {0 , 0}); 
    for(int i = 1 ; i <= n ; i++)
    {
        a1[i].z = i ; 
    }
    for(int i = 1 ; i <= m ; i++)
    {
        a2[i].z = i ; 
    }
    while(d--)
    {
        int x1 , y1 , x2 , y2 ;  cin >> x1 >> y1 >> x2 >> y2 ; 
        if(x1 == x2)
        {
            a2[min(y1 , y2)].num++;
        }
        else if(y1 == y2)
        {
            a1[min(x1 , x2)].num++;
        }
    }
    sort(all(a1) , cmp);
    sort(all(a2) , cmp);
    vector<jo>ans1;
    vector<jo>ans2; 
    for(int i = 0 ; i < k ; i++)
    {
        ans1.push_back(a1[i]);
    }
    for(int i = 0 ; i < l ; i++)
    {
        ans2.push_back(a2[i]);
    }
    sort(all(ans1),cmp1);
    sort(all(ans2),cmp1);
    for(int i = 0 ; i < k ; i++)
    {
        cout << ans1[i].z ; 
        if(i != k -1)
        {
            cout << " " ; 
        }
    }
    cout << endl ; 
    for(int i = 0 ; i < l ; i++)
    {
        cout << ans2[i].z ;
        if(i != l - 1)
        {
            cout << " " ; 
        } 
    }
}
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--) 
    {
        work();
    }
    return 0;
}