來源：牛客網(wǎng)：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 51200K，其他語言102400K 64bit IO Format: %lld

題目描述

上課的時候總有一些同學(xué)和前后左右的人交頭接耳，這是令小學(xué)班主任十分頭疼的一件事情。不過，班主任小雪發(fā)現(xiàn)了一些有趣的現(xiàn)象，當(dāng)同學(xué)們的座次確定下來之后，只有有限的D對同學(xué)上課時會交頭接耳。同學(xué)們在教室中坐成了M行N列，坐在第i行第j列的同學(xué)的位置是（i，j），為了方便同學(xué)們進(jìn)出，在教室中設(shè)置了K條橫向的通道，L條縱向的通道。于是，聰明的小雪想到了一個辦法，或許可以減少上課時學(xué)生交頭接耳的問題：她打算重新擺放桌椅，改變同學(xué)們桌椅間通道的位置，因為如果一條通道隔開了兩個會交頭接耳的同學(xué)，那么他們就不會交頭接耳了。
請你幫忙給小雪編寫一個程序，給出最好的通道劃分方案。在該方案下，上課時交頭接耳的學(xué)生對數(shù)最少。

輸入描述:
第一行，有5各用空格隔開的整數(shù)，分別是M，N，K，L，D（2 ≤ N，M ≤ 1000，0 ≤ K < M，0 ≤ L < N，D ≤ 2000）。
接下來D行，每行有4個用空格隔開的整數(shù)，第i行的4個整數(shù)Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)與(Pi,Qi)的兩個同學(xué)會交頭接耳（輸入保證他們前后相鄰或者左右相鄰）。
輸入數(shù)據(jù)保證最優(yōu)方案的唯一性。

輸出描述:
第一行包含K個整數(shù)，a1a2……aK，表示第a1行和a1+1行之間、第a2行和第a2+1行之間、…、第aK行和第aK+1行之間要開辟通道，其中ai < ai+1，每兩個整數(shù)之間用空格隔開（行尾沒有空格）。
第二行包含L個整數(shù)，b1b2……bk，表示第b1列和b1+1列之間、第b2列和第b2+1列之間、…、第bL列和第bL+1列之間要開辟通道，其中bi< bi+1，每兩個整數(shù)之間用空格隔開（行尾沒有空格）。
示例1
輸入
復(fù)制
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
輸出
復(fù)制
2
2 4
說明

上圖中用符號*、※、+ 標(biāo)出了3對會交頭接耳的學(xué)生的位置，圖中3條粗線的位置表示通道，圖示的通道劃分方案是唯一的最佳方案。

題解：

沒兩個可以溝通的學(xué)生，之間只有唯一連接，斷開行或列即可，統(tǒng)計每一行能阻斷多少學(xué)生，每一列能阻斷多少學(xué)生，排序即可

代碼：

#include <bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; const int maxn = 2e6 + 6; const int mod = 998244353; typedef pair<int,int> p; p col[maxn],row[maxn]; //first表示次數(shù) //second表示插入的位置 bool cmp(p a,p b) {return a.first>b.first; } int n,m,k,l,q; int main() {cin>>n>>m>>k>>l>>q;for(int i=1; i<=n; i++)row[i].second=i;for(int i=1; i<=m; i++)col[i].second=i;while(q--) {int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);if(x1==x2)col[min(y1,y2)].first++;else row[min(x1,x2)].first++;}sort(row+1,row+n+1,cmp);multiset<int>ans;for(int i=1; i<=k; i++)ans.insert(row[i].second);for(auto v:ans) {printf("%d ",v);}printf("\n");ans.clear();sort(col+1,col+m+1,cmp);for(int i=1; i<=l; i++)ans.insert(col[i].second);for(auto v:ans) {printf("%d ",v);}printf("\n"); }

總結(jié)

以上是生活随笔為你收集整理的【每日一题】8月10日题目精讲—排座椅的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。