题解 P6490 【[COCI2010-2011#6] RAZINE】

追梦之鲸 · 2021-01-02 21:16:38 · 题解

本蒟蒻的第002篇题解。

经典回顾P6490

思路

这道题是一个很简单的贪心题。

直解从n-1倒序枚举即可。

详解

• 首先这到题必须严格递增，也就是没个数必须比下个数小，比上个数大，相等不行！

• 说一下为什么从n-1倒序枚举，而不从1正序枚举？对于不懂这类的同学（比如窝），可能窝给出一组数据你们大概就能理解：

  5 6 7 4

  这组数据用刚才正序枚举的思想的话答案是0，实际答案是12。

可能还有同学不懂，那么下面我会更详细的解说：

这题说需要求出所有减去的数的总和的最小值，所以必须保证最后面的数最大（你可以理解为最后的数不变）。

然后从第n-1个数起，如果第i个数比第i+1个数大，第i个数就等于第i+1个数-1。

还有这里介绍一下可能对你有帮助的register int和快读快输

链接

• register int

这个register int中的register 表示使用cpu内部寄存器（寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件）的变量，而平时的int是把变量放在内存中，存到寄存器中可以加快变量的读写速度。

• 快读与快输

链接

模板

//快读
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
}
//快输
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
或
inline int write(int X)
{
    if(X<0) {putchar('-'); X=~(X-1);}
    int s[20],top=0;
    while(X) {s[++top]=X%10; X/=10;}
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}

code：

#include<bits/stdc++.h>//无敌头文件！
#define ll long long
#define il inline
#define ri register int
using namespace std;
il int rd(){
   int s=0;
   char ch=getchar();
   while(ch<'0'||ch>'9') ch=getchar();
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s;
}
il void wt(int x){
    if(x>9) wt(x/10);
    putchar(x%10+'0');
    return;
}
//快读与快输
int n,a[101],dan;
int main(){
    n=rd();
    for(ri i=1;i<=n;i++) a[i]=rd();
    //本题的精髓
    for(ri i=n-1;i>=1;i--) if(a[i]>=a[i+1]){dan+=a[i]-a[i+1]+1;a[i]=a[i+1]-1;}
    wt(dan);
    return 0;
    撒花✿✿ヽ(°▽°)ノ✿
}

最后管理大大求过&&来玩啊