UVa 11549 Open Credit System-白红宇

UVa 11549 Open Credit System

阅读量：5235 次

发布时间：2019-06-14

本文共 1561 字，大约阅读时间需要 5 分钟。

题意：给出n个数，找出两个整数a[i],a[j](i < j),使得a[i] - a[j]尽量大

从小到大枚举j,在这个过程中维护a[i]的最大值

maxai晚于ans更新，

可以看这个例子

1 8 9 10 11

正确的应该是-1

如果更早更新的话，算出来就是0

用数组来存的

1 #include
      
          2 #include
       
           3 #include
        
           4 #include 
         
            5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std;12 13 typedef long long LL;14 const int INF = (1<<30)-1;15 const int mod=1000000007;16 const int maxn=1000005;17 18 int a[maxn];19 int n;20 21 int main(){22 int T;23 scanf("%d",&T);24 while(T--){25 scanf("%d",&n);26 for(int i = 0;i < n;i++) scanf("%d",&a[i]);27 int ans = a[0] - a[1];28 int maxai = a[0];29 for(int j = 1;j < n;j++){30 ans = max(ans,maxai - a[j]);31 maxai = max(maxai,a[j]);32 // printf("j = %d maxai = %d ans = %d\n",j,maxai,ans);33 }34 printf("%d\n",ans);35 }36 return 0;37 }

View Code

边读边算的

1 #include
      
          2 #include
       
           3 #include
        
           4 #include 
         
            5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std;12 13 typedef long long LL;14 const int INF = (1<<30)-1;15 const int mod=1000000007;16 const int maxn=1000005;17 18 int main(){19 int T;20 scanf("%d",&T);21 while(T--){22 int n;23 scanf("%d",&n);24 25 int x,y,ans;26 scanf("%d %d",&x,&y);27 ans = x-y;28 int maxai = x;29 for(int i = 2;i