Nebius Welcome Round (Div. 1 + Div. 2) D Accommodation
作者:
图灵机
,
2023-03-17 18:45:16
,
所有人可见
,
阅读 208
**题意:**
有个n * m的窗户矩阵,0表示灯没亮,1表示灯亮了,m%4 == 0,每层有m / 2个单间和m / 4个双间,双间的窗户是两个连续的窗户,单间的窗户是单个的窗户,问这个楼最少和最多就几个住户
**题解:**
先考虑最少有几个住户,因为双间和单间个数是固定的,所以影响最终住户个数的关键是双间的位置,如果双间住一个住户就浪费了,所以对于连续的1,安排一个双间,one表示这一层1的个数
分两种情况:
第一种,连续1的个数大于m/4,这时候mn += one - m / 4
第二种,连续1的个数小于m/4,这时候mn += one - cnt11
然后考虑最多有几个住户,这时候就要尽可能让双间浪费掉,也就是说01,10,00这三种情况全部安排给双间,住户个数就能最多。
分两种情况:cnt01表示01,11,00的个数
第一种,01,10,00的个数大于m/4,这时候mn += one
第二种,01,10,00的个数小于m/4,这时候mn += one - (m / 4 - cnt01)
**code:**
`void solve()
{
// cin>>n>>k;
cin>>n>>m;
int mn = 0,mx = 0;
fo(i,1,n) {
string s;cin>>s;
int one = 0;
for(int j = 0;j < s.size();j ++ ) {
if(s[j] == '1') one ++ ;
}
int cnt11 = 0;
int m1 = m / 4;
bool ok = 1;
for(int j = 0;j <= m - 2;j ++ ) {
if(s[j] == '1' && s[j + 1] == '1') {
cnt11 ++ ;
j ++ ;
}
if(cnt11 >= m1) {
ok = 0;
break;
}
}
if(!ok) {
mn = mn + (one - 2 * m1) + m1;
} else {
mn = mn + (one - 2 * cnt11) + cnt11;
}
ok = 1;
int cnt01 = 0;
for(int j = 0;j <= m - 2;j ++ ) {
if(s[j] == '1' && s[j+1] == '0') {
cnt01 ++ ;
j ++ ;
} else if(s[j] == '0' && s[j+1] == '1') {
cnt01 ++ ;
j ++ ;
} else if(s[j] == '0') {
cnt01 ++ ;
j ++ ;
}
if(cnt01 >= m1) {
ok = 0;
break;
}
}
if(!ok) {
mx = mx + one;
} else {
mx = mx + (one - (m1 - cnt01));
}
// db(one)
// dbbb(m1,cnt01,one - (m1 - cnt01) * 2)
}
cout<<mn<<' '<<mx<<endl;
}`
PS:感觉有一个多月没刷题了,明天要打练习赛特意刷一下,但一道D题就花了一小时QAQ
终于盒到学长的cf账号了(得意)ヾ(≧▽≦*)o
QAQ