返回题解分享
讨论 / 题解分享/ 帖子详情

水质检测 - 题解

贪心大致分为两种:
对于情况1:
#...
...#
都是放三个,但是

#..#
...# (中间省略了)


#...
#..#(中间省略了)

更优。

对于情况二:

#...#
#....
肯定是将第一排填满最优。


#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s[2];
  cin>>s[0];
  cin>>s[1];
  int len = s[0].size();
  int ans = 0;
  int l = -1, r = -1;
  for(int i = 0;i<len;i++)
    if(s[0][i] == '#' || s[1][i] == '#')
    {
      l = i;
      break;
    }
  for(int i = l + 1;i<len;i++)
    if(s[0][i] == '#' || s[1][i] == '#')
    {
      r = i;
      break;
    }

  if(r == -1 || l == -1)
  {
    cout<<0;
    return 0;
  }

  for(int i = r + 1;i<=len;i++)
    if(i == len || s[0][i] == '#' || s[1][i] == '#')
    {
      if((s[0][r] == '#' && s[1][r] == '#') || (s[0][l] == '#' && s[1][l] == '#'))
        ans += r - l - 1;
      else if(s[0][r] == '#')
      {
        if(s[1][l] == '#')
        {
          ans += r - l;
          s[1][r] = '#';
        }
        else if(s[0][l] == '#')
          ans += r - l - 1;
      }
      else if(s[1][r] == '#')
      {
        if(s[0][l] == '#'){
          ans += r - l;
          s[0][r] = '#';
        }
        else if(s[1][l] == '#')
          ans += r - l - 1;
      }
      l = r;
      r = i;
    }
  
  cout<<ans;
  return 0;
}
0 回复 0 转发 1 喜欢 3 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!