别人的思路;
- 对于第一个问题求最小: 尽可能让连续的2个1放一个房间就行,最多m/4
- 对于第二个问题: 尽可能让不是11连续的位置为 double公寓, 因为每有2个1就会减少一个 ans,(先想出所有的1然后利用减法思维,很巧妙)
- 2个2个判断的时候 +2的思想很妙
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; using LL = long long; int main(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n, m; cin >> n >> m; int mn = 0, mx = 0; while(n--){ string s; cin >> s; int cnt1 = count(s.begin(), s.end(), '1'); { int cnt11 = 0; for(int i = 0; i < m; i++){ if (s[i] == '0') continue; if (i + 1 < m && s[i + 1] == '1'){ cnt11 += 1; i++; } } mn += cnt1 - min(cnt11, m / 4); } { int cnt00 = 0; for(int i = 0; i < m; i++){ if (i + 1 < m && ((s[i] != s[i + 1]) || s[i] == '0')){ cnt00 += 1; i++; } } if (cnt00 <= m / 4){ mx += cnt1 - (m / 4 - cnt00); } else{ mx += cnt1; } } } cout << mn << ' ' << mx << '\n'; }View Code
标签:cnt11,CF21804D,int,cnt00,cin,++,include,Accommodation,贪心 From: https://www.cnblogs.com/Lamboofhome/p/17213299.html