CodeForces 982 D Shark

Shark

题意：一个研究员观察了一条鲨鱼n天的运动，然后这条鲨鱼他只会往前走，不会回到去过的地方，现在有一个k,，如果鲨鱼当天游过的距离 >= k, 代表的鲨鱼在这天会前往下一个地点，现在求鲨鱼在每个停留的地点所待的时间是一样的，然后在上面那个情况下使得鲨鱼所待得地点数目最多，然后再地点数目的情况下保证K最小。

题解：从小到大处理元素，每次将k = 当前元素+1，因为只有k比一个元素大了才会有新的停留地点，然后对于所有出现过的元素鲨鱼都会在这个点停留，然后我们需要对每一段连续的停留片段计算出他的天数，然后check一下是否合法，我们可以用并查集将连续的片段合并记录长度来优化check，用set记录有几个片段，然后当片段数目 > 答案中的岛就check一下，如果成立，更新答案。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 const int N = 1e5+;

 int n;

 int pre[N];

 int cnt[N];

 int vis[N];

 int ss[N];

 struct Node{

     int t;

     int id;

 }A[N];

 bool cmp(Node x,Node y){

     return x.t < y.t;

 }

 set<int>s ;

 bool check(){

     int ttt = *s.begin();

     return ss[cnt[ttt]] == s.size();

 }

 int Find(int x){

     if(x == pre[x]) return x;

     return pre[x] = Find(pre[x]);

 }

 int main(){

     scanf("%d", &n);

     int ans = INF;

     int len = ;

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

         cnt[i] = ;

         pre[i] = i;

     }

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

         scanf("%d", &A[i].t);

         ans = min(ans,A[i].t+);

         A[i].id = i;

     }

     sort(A+,A++n,cmp);

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

         int now = A[i].id;

         vis[now] = ;

         int f = ;

         if(now+ <= n && vis[now+]){

             int t = Find(now), y = Find(now+);

             pre[t] = y;

             ss[cnt[y]]--;

             cnt[y] += cnt[t];

             ss[cnt[y]]++;

             f = ;

         }

         if(now- >=  && vis[now-]){

             int t = Find(now), y = Find(now-);

             if(f == ) s.erase(t),ss[cnt[t]]--;

             ss[cnt[y]]--;

             cnt[y] += cnt[t];

             ss[cnt[y]]++;

             pre[t] = y;

             f =  ;

         }

         if(f == ) s.insert(now), ss[cnt[now]]++;

         if(s.size() > len && check()){

             len = s.size();

             ans = A[i].t+;

         }

     }

     printf("%d", ans);

     return ;

 }