题解 P5146 【最大差值】

kevin_y · 2019-08-23 12:47:18 · 题解

我这应该是最快解法吧（千万别被dalao打脸

这题是用贪心来求解的，先找出最小值，然后在下一个最小值出现前，最大数减最小数就是最优解（本人语文不好，描述能力差

还是看栗子吧

输入:

  5
  3 4 10 1 5

1. 先找出的最小值是3，然后到下一个最小值前，最大差值是10-3=7。
2. 发现1比3小，最小值变为1,。但在后面数中最大数-1小于7 （5-1=4<7）
3. 所以最大差值是7。
4. 不懂的可以看代码手推下。

   #include<iostream>
   #include<cstdio>
   using namespace std;
   int mi=1<<30,ma=-1<<30,n,k;//mi保存最小值，ma保存最大差值
   inline int read(){//快速读入
   int f=1,x=0;
   char s=getchar();
   while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
   while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
   return x*f;
   }
   inline int min(int a,int b){//手打会快些
   return a<b?a:b;
   }
   inline int max(int a,int b){
   return a>b?a:b;
   }
   int main(){
   n=read();
   for(int i=1;i<=n;i++){
       k=read();
       mi=min(mi,k); //mi存下当前最小值
       ma=max(ma,k-mi);//k-mi是当前最小值与其后面数的差值
   }
   cout<<ma<<endl;
   }

   //不懂的私信问我