Problem
小b养了n盆花,第i盆花高度为A[i]。
小b每天可以给某一盆花浇水,这样这盆花就会长高一单位。
小b希望每盆花都是独一无二的,也就是不存在两盆花高度相等。
求小b最少要浇几天水。
Solution
冲着一个浇水和把一个浇到一个高度,再浇这个高度的一盆是一样的。
因此如果𝑎[𝑖+1]<=𝑎[𝑖],则让𝑎[𝑖+1]=𝑎[𝑖]+1。
由于a[i]只有40000,可以每个高度做标记然后找。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<iostream> #include<stdio.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cstring> #include<stack> #define mem(ss) memset(ss,0,sizeof(ss)) typedef long long ll; typedef long double ld; typedef __int128 lll; const ll mod=1e9+7; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;} int n,ans,cnt; struct E{ int a,pla; }; E h[40020]; E b[40020]; int cmp1(E x,E y){ return x.a<y.a; } int cmp2(E x,E y){ return x.pla<y.pla; } bool f[80020]; int main(){ io_opt; cin>>n; for(int i=1;i<=n;i++){ cin>>h[i].a; f[h[i].a]=true; h[i].pla=i; } sort(h+1,h+1+n,cmp1); for(int i=2;i<=n;i++){ if(h[i].a<=h[i-1].a){ ans+=h[i-1].a+1-h[i].a; h[i].a=h[i-1].a+1; } } cout<<ans<<endl; return 0; }
|