woj 1567 - D - Sloth's Angry（贪心）

题意：

思路：

 

复制代码#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<stdlib.h> #include<algorithm> #include<queue> #include<vector> #include<ctype.h> #define LL __int64 using namespace std; const int MAXN=1000+5; const int INF=0x3f3f3f3f; int a[MAXN],id,n; bool judge(int a[]) { int Minn=INF; for(int i=0;i<n;i++) if(a[i]!=0 && a[i]<Minn) { Minn=a[i]; id=i; } if(Minn==INF) return false; else return true; } int main() { while(scanf("%d",&n)!=EOF) { int minn=INF; for(int i=0;i<n;i++) { scanf("%d",&a[i]); if(a[i]<minn) minn=a[i]; } int cnt=1; for(int i=0;i<n;i++) a[i]=a[i]-minn; while(judge(a)) { int minnum=a[id]; for(int i=id;i>=0;i--) { if(a[i]==0) break; a[i]=a[i]-minnum; } for(int i=id+1;i<n;i++) { if(a[i]==0) break; a[i]=a[i]-minnum; } cnt++; } printf("%dn",cnt); } return 0; }

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
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctype.h>
#define LL __int64
using namespace std;
const int MAXN=1000+5;
const int INF=0x3f3f3f3f;
int a[MAXN],id,n;
bool judge(int a[])
{
    int Minn=INF;
    for(int i=0;i<n;i++)
        if(a[i]!=0 && a[i]<Minn)
        {
            Minn=a[i];
            id=i;
        }
    if(Minn==INF) return false;
    else return true;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int minn=INF;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]<minn) minn=a[i];
        }
        int cnt=1;
        for(int i=0;i<n;i++) a[i]=a[i]-minn;

        while(judge(a))
        {
            int minnum=a[id];
            for(int i=id;i>=0;i--)
            {
                if(a[i]==0) break;
                a[i]=a[i]-minnum;
            }
            for(int i=id+1;i<n;i++)
            {
                if(a[i]==0) break;
                a[i]=a[i]-minnum;
            }
            cnt++;
        }
        printf("%dn",cnt);
    }
    return 0;
}