AcWing 5438. 密接牛追踪2 区间覆盖标题的具体表明

5438. 密接牛追踪2 - AcWing题库
题意：盘算用最少的点覆盖1的区间；
思绪：记每一个一连的1的区间长度为cnt，则cnt=(2*day+1)*点的个数，以是点的个数就是 cnt/(2*day+1) 上取整(要覆盖完)，可知day越大,所需的点的个数越小,因此要最大化day；即盘算每个一连1的区间的最大day取交集,再用记录的以是cnt和maxday盘算出最少的点的数目；   盘算区间maxday时，分环境讨论[区间在中心时,由于两边有0，2*maxday<= cnt 以是maxday=(cnt -1)/2]，[区间在两边时,maxday=cnt-1，即从一端开始扩展]

3. const int N = 3e5 + 10,T = 20;
5. int n;
6. char s[N];
7. vector<int> cnt;//所有连续1的区间长度
9. void solve()
10. {
11.         cin >> n;
12.         for (int i = 1;i <= n;i ++) cin >> s[i];
13.        
14.         int maxday = n;
15.         for (int i = 1;i <= n;i ++)
16.         {
17.                 if (s[i] == '0') continue;
18.                 int j = i + 1;//第一天是1
19.                 while(j <= n && s[j] == '1') j ++;
20.                 int sum = j - i;//连续1的长度
21.                 cnt.push_back(sum);
22.                 int day = (sum - 1) / 2;//假设为中间的情况
23.                 if (i == 1 || j == n + 1) day = sum - 1;//是两边的情况
24.                 maxday = min(maxday,day);//取交集
25.                 i = j;
26.         }
27.         LL ans = 0;
28.         for (auto &t : cnt)
29.         {
30.                 ans += (t + 2 * maxday) / (2 * maxday + 1);
31.         }
32.        
33.         cout << ans << endl;
34. }       

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告