从教程上看到是用贪心的思想求解, 但是自己途中还不求错了。
原因是两排,每两个房间只对应一个过道。然后我们对过道计数即可。
贪心的想法就是每次我选重叠最多的过道进行搬。
#include<iostream> #include<cstdio> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<cstring> #include<cmath> #include<fstream> typedef long long ll; #define cl(a,n) memset(a,n,sizeof a ) using namespace std; /**************************** By:七柳先森丶 Date: 1.4 2015 *****************************/ const int mx=210; //贪心,贪心策略为每次只选交叉最多的边交集。。 int gd[mx]; int main() { int T; scanf("%d",&T); while(T--){ int N; for(int j=0;j<200;j++) gd[j]=0; scanf("%d",&N); int a,b,min1=-1; for(int i=1;i<=N;i++){ scanf("%d%d",&a,&b); //比较坑的一点,a有可能比b大。 //还有就是除以2,二排房子,一个走道,对面的可以直接搬。。 //对面的点只算一个点。 //只计算一个过道被点用的次数。 //如果用房间代表过道,则有可能不会有重叠。 int begin=(a-1)/2; int end=(b-1)/2; if(begin > end) swap(begin,end); for(int i1=begin;i1<=end;i1++) gd[i1]++; } for(int i=0;i<200;i++){ if(gd[i]>min1) min1=gd[i]; } printf("%d\n",min1*10); } //system("pause"); return 0; }