1169C
1700的题,然而比赛的时候没有做出来。。
题意:给你一个n表示序列长度为n,还有一个m表示这个序列的最大值小于m
然后对这个数组进行多次操作,一次操作为 对ai,aj,ap,等k个数进行+1且对m取模,最后让这个序列变成一个不递减的序列,可以证明通过x次操作你是一定可以使这个数组符合条件,现在的问题是求得最少的操作次数x。
思路:从题意可以看出这个题目的答案一定是在0~m之间,因为对于任何一个数组操作至多m次之后都可以变成0000的数组,所以对答案进行二分,然后对每个操作次数x进行分析,可以得出以下结论:
mx表示前i个数的最大值
1、如果这个数小于前面数组的最大值,那么只需要a[i]+x>=mx就行
2、如果这个数大于前面数组的最大值,那么如果这个数
a[i]+x>m :表示取模之后变小了,这里又分两种情况:
1、如果a[i]+x-m<mx, 意味着如果不进行更新,a[i]就不能等于mx,所以要进行更新,即mx=a[i].
2、如果a[i]+x-m>=mx,就意味着,我可以不加那么多x,即mx不进行更新
a[i]+x<m:如果加上x之后没有变小,那么需要更性mx的值,即mx=a[i]。
这种情况综上可以得出,如果a[i]+x-m<mx,那么mx需要进行更新,反之这不要,代码就出来了。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define per(i, a, n) for(int i = n-1; i >= a; i--)
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define INF 1ll<<60
#define fopen freopen("file.in","r",stdin);freopen("file.out","w",stdout);
#define fclose fclose(stdin);fclose(stdout);
#define PI 3.14159265358979323846
const int maxn = 3e5+10;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int a[maxn];
int n, m;
bool check(int x){
int mx=0;
for(int i = 0; i < n; i++){
if(a[i]<=mx){
if(mx-a[i]>x){
return 0;
}
}else {
if(a[i]+x-m<mx) mx=a[i];
}
}
return 1;
}
int main(){
n=read(), m=read();
for(int i = 0; i < n; i++) a[i]=read();
int l = 0, r=m;
int ans = 0;
while(l<=r){
int mid = (l+r)/2;
if(check(mid)){
ans = mid;
r = mid-1;
}else l = mid+1;
}
printf("%d\n", ans);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)