题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 2010
typedef pair<int,int> PII;
PII row[N],col[N];
int ans[N];
int main()
{
    int i,m,n,k,l,d,x1,x2,y1,y2,cnt;
    cin>>m>>n>>k>>l>>d;
    for(i=1;i<=m;i++)
    {
        row[i].second=i;  //初始化横向分隔线
    }

    for(i=1;i<=n;i++)
    {
        col[i].second=i;  //初始化纵向分隔线
    }

    while(d--)
    {
        cin>>x1>>y1>>x2>>y2;
        if(abs(x1-x2)==1)
        {
            row[min(x1,x2)].first++;  //统计一条横向分隔线能分隔多少对说话的同学
        }
        if(abs(y1-y2)==1)
        {
            col[min(y1,y2)].first++;  //统计一条纵向分隔线能分隔多少对说话的同学
        }
    }

    sort(row+1,row+m+1);  //按横向分隔线能够分隔的同学对数从小到大排序
    sort(col+1,col+n+1);  //按纵向分隔线能够分隔的同学对数从小到大排序

    cnt=0;
    for(i=m;i>m-k;i--)  //取出k条最优横向分隔线
    {
        ans[cnt++]=row[i].second;
    }
    sort(ans,ans+cnt);  //按照横向分隔线的标号从小到大排序
    for(i=0;i<cnt;i++)
    {
        cout<<ans[i];
        if(i<cnt-1)
        {
            cout<<' ';
        }
    }
    cout<<endl;

    cnt=0;
    for(i=n;i>n-l;i--)  //取出l条最优纵向分隔线
    {
        ans[cnt++]=col[i].second;
    }
    sort(ans,ans+cnt);  //按照纵向分隔线的标号从小到大排序
    for(i=0;i<cnt;i++)
    {
        cout<<ans[i];
        if(i<cnt-1)
        {
            cout<<' ';
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla