B 减成一“科林明伦杯”哈尔滨理工大学第十届程序设计竞赛(同步赛)

比赛链接
B 减成一题目链接

题意：
存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。
数据保证一定有解。
(也就是这个题本身)

题解：知识点：暴力枚举

直接从头到尾跑一遍就行了。
我们这样想；

1.如果前面那个数比这个数大，那我们是在前一个数区间减1是肯定可以带着这个数一起减一就是区间向右扩一。所以这个数就不产生代价。
2.如果前面那个数比这个数小，那我们扩展区间是只能扩到前一个数这么大，至于这个数比前一个数大的那部分还要减去，就产生(a[i]-a[i-1])这么多代价。

都减一是因为把他们都化成零，这样直接一遍for 就行了，或者吧第一个数前面那个数赋值成1，这样保证最后结果都是1。两种方发都可以。

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()
int main(){
     t=read;
    while(t--){
       n=read;
       for(int i=1;i<=n;i++)
       {
           a[i]=read;
           a[i]=a[i]-1;
        }
        sum=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>=a[i-1]){
                sum+=a[i]-a[i-1];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

两种没什么大区别，就变了一个地方。

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=998244353;
const int MOD=10007;

inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}

/*priority_queue<ll , vector<ll> , greater<ll> > mn;//上  小根堆         小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下       大根堆      大到小
map<ll,ll>mp;*/

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;

#define read read()
int main(){
     t=read;
    while(t--){
       n=read;
       for(int i=1;i<=n;i++)
       {
           a[i]=read;
        }
        sum=0;
        a[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(a[i]>=a[i-1]){
                sum+=a[i]-a[i-1];
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}