标签：CSP202109 int MAX sum 非零段 ans 500010

CSP202109_2

目录

• CSP202109_2
  • 题目
  • 思路
    • 暴力
    • 差分优化
  • Code

题目

非零段划分

思路

暴力

直接暴力，依次枚举所有可能的 p，针对当前 p 遍历序列求非零段个数。时间复杂度\(O(n^2)\)，70pts

差分优化

考虑从序列最大值开始设定 p， p 逐渐减小。

当 h[i] < p 且其两侧都还不是非零段时，其开始成为非零段，非零段数量相对于 p + 1 时增加。

当 h[i] < p 且其两侧都已经是非零段时，其成为非零段导致了原来已存在的两个非零段合成为一个，非零段数量相对于 p + 1 时较少。

显然就是一个差分的关系，且要求逆序求解。

一些注意点：

• 因为连续且相等的数会同时成为非零段，因此进行去重操作。
• 因为序列两端都可以在不为 0 时直接做非零段，因此为令去重后序列两端点可以正确计算，在去重时通过包含 h[0] 与 h[n + 1]以达目的。

关于上面第二个注意点，自己在开始写时是通过额外特判实现的。下文代码中即使用了去重时的操作，该思路借鉴于这位大佬。

相比于前些年CSP对于前缀和直接明显的考察，这道题在模型构建上增大了一些思维含量。

Code

1. 暴力(70pts)

   #include<bits/stdc++.h>
   
   using namespace std;
   
   int n, MAX;
   int h[500010];
   int p[500010];
   int ans;
   int main()
   {
   	cin >> n;
   	for(int i = 1; i <= n; i++)
   	{
   		cin >> h[i];
   		MAX = max(MAX, h[i]);
   	}
   	for(int k = 1; k <= MAX; k++)
   	{
   		int sum = 0;
   		for(int i = 1; i <= n; i++)
   		{
   			if(h[i] < k && h[i - 1] >= k)
   			{
   				sum++;
   			}
   			if(i == n && h[i] >= k)
   			{
   				sum++;
   			}
   		}
   		ans = max(ans, sum);
   	}
   
   	cout << ans;
   	return 0;
   }
   

2. 差分(100pts)

   #include<bits/stdc++.h>
   
   using namespace std;
   
   int n, MAX;
   int h[500010];
   int p[500010];
   int ans;
   
   int main()
   {
   	cin >> n;
   	for(int i = 1; i <= n; i++)
   	{
   		cin >> h[i];
   		MAX = max(MAX, h[i]);
   	}
   	int len = unique(h, h + 2 + n) - h;
   	//cout << len << endl;
   	for(int i = 1; i < len; i++)
   	{
   		//cout << h[i] << " ";
   		if(h[i] > h[i - 1] && h[i] > h[i + 1]) p[h[i]]++;
   		if(h[i] < h[i - 1] && h[i] < h[i + 1]) p[h[i]]--;
   	}
   	int sum = 0;
   	for(int i = MAX; i >= 1; i--)
   	{
   		sum += p[i];
   		ans = max(ans, sum);
   	}
   	cout << ans;
   	return 0;
   }
   

标签：CSP202109,int,MAX,sum,非零段,ans,500010
From： https://www.cnblogs.com/kevin-chance/p/16723906.html