题目链接:https://codeforces.com/contest/1804/problem/D
差点做出来的D题了,两千分的难题!
大意是存在n层楼,每个楼有m个窗户,存在m/4个两居室和m/2个单居室,双居室一个灯亮就视为这个居室亮灯了
询问每层楼最少亮灯的居室和,每层楼最多亮灯的居室和。
最少的已经是求出来了!
重点在于最多的居室。
最多居室 = 亮灯的数量 - (双居室的数量 - 我们所求出来的最优匹配到的双居室数量,最低为0)。
code!:
void solve() { int n,m; cin>>n>>m; vector<int> a[n]; for(int i=0;i<n;i++){ string s; cin>>s; for(int j=0;j<s.size();j++) a[i].push_back(s[j]-'0'); a[i].push_back(1000); } int maxt = 0; for(int i=0;i<n;i++){ int ks = 0;//空着的两居室 int cnt = 0;//亮着的 for(int j=0;j<m;j++){ if(a[i][j]==1) cnt++; if(j<m-1){ if(a[i][j]==0||a[i][j+1]==0){//如果至少存在两个中有一个为0,那么我们令这是一个两居室 j++; if(a[i][j]==1)cnt++; ks++; } } } ks = min(ks,m/4); maxt+=cnt-(m/4-ks);//答案等于 亮着的数量 - (两居室的总数量-匹配到的最优两居室的数量,结果最少为0) } int mint = 0; for(int i=0;i<n;i++){ int d=0,s=0; for(int j=0;j<m;){ if(a[i][j]==1){ if(a[i][j]==a[i][j+1]){ s++; j+=2; }else d++,j++; }else j++; } if(s>m/4){ mint+=m/4+(s-m/4)*2+d; }else mint+=(s+d); } cout<<mint<<' '<<maxt<<endl; }