河南省赛------＞B.Art for Rest

一，思路：

1.根据题目要求，我们要判断当数组被分成了(n+k-1)/k (向上取整) 段，前面的每一段里面的元素是否都要比后面每一段多要小（在每一段的内部我们是不需要考虑的，题目已经要求了是有序的，所以我们只要比较前面的一段的最大值和后面最小值的关系即可）。

2.上面这一点是很好想到的，但是要在规定时间复杂度下实现，就有点难想到的。我们这里是利用前缀最大值和后缀最小值（类前缀和）来实现的。我们只需要枚举两两区间的边界点，根据这个点的前缀最大值 mx和后缀最小值 mi 比较。

（1）如果 mx > mi : 说明肯定存在一个点是逆序的，则不符合题目要求.

（2）如果mx<mi : 说明前的最大值都比后面最小小了，那么前面任何一个元素都小于等于后面的元素。

3.时间复杂度：我算着好像是超了，但是过了，有大佬可以分析以下吗？

二，代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <vector>
using namespace std;

const int N = 1e6 + 10, M = 1e9 + 7;

typedef long long ll;
typedef pair<int, int> pii;

ll arr[N];
ll mx[N],mi[N];

void Solved()
{
   int n;
   cin>>n;

   for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
   
//前缀最大值
   mx[1]=arr[1];
   for(int i=2;i<=n;i++) mx[i]=max(arr[i],mx[i-1]);
   
//后缀最小值
   mi[n]=arr[n];
   for(int i=n-1;i>=1;i--) mi[i]=min(arr[i],mi[i+1]);
   
   ll res=0;

   for(int i=1;i<=n;i++){

      int flag=0;

//枚举每个区间末尾下标,如果有一个不符合要求的，就说明这个方案不行
      for(int j=i;j<n;j+=i){
         if(mx[j]>mi[j+1]){
            flag=1;
            break;
         }
      }

      if(flag==0) res++;
   }

   cout<<res<<endl;

}

int main()
{
   int t;
   t=1;

   while (t--)
   {
      Solved();
   }
   return 0;
}

原文地址：https://blog.csdn.net/qq_75103498/article/details/137913396

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！