贪心局限性

本文主要是介绍贪心局限性，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://codeforces.com/contest/1561/problem/C 题目链接

t个测试样例，每个测试样例n个洞穴，接下来n行每行第一个m为该洞穴怪兽个数，接下来 m个数字为怪兽护甲，当且仅当英雄的能力大于怪兽护甲时才能击败该怪兽，击败后能力加1;

错误代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[100010];
 4 struct node
 5 {
 6     int minn;
 7     int maxx;
 8     int sum;
 9 }b[100010];
10 int cnt;
11 bool cmp(node a,node b)
12 {
13     return a.minn<b.minn;
14 }
15 int main()
16 {
17     ios::sync_with_stdio(false);
18     cin.tie(0);
19     cout.tie(0);
20     int t;
21     cin>>t;
22     while(t--)
23     {
24         cnt=0;
25         int k;
26         cin>>k;
27         while(k--)
28         {
29             int n;
30             cin>>n;
31             cin>>a[1];
32             int minn=a[1]+1;
33             int now=a[1]+2;
34             for(int i=2;i<=n;i++)
35             {
36                 cin>>a[i];
37             }
38             for(int i=2;i<=n;i++)
39             {
40                 //cin>>a[i];
41                 if(a[i]>=now)
42                 {
43                     minn=a[i]-i+2;
44                     //cout<<minn<<endl;
45                     now=a[i]+2;
46                 }
47                 else now++;
48                 //cout<<minn<<' '<<now<<endl; 
49             }
50             b[++cnt].minn=minn;
51             b[cnt].maxx=now;
52             b[cnt].sum=n;
53             //cout<<b[cnt].minn<<' '<<b[cnt].maxx<<' '<<endl;
54         }
55         sort(b+1,b+1+cnt,cmp);
56         int now=b[1].maxx;
57         int sum=b[1].sum;
58         int ans=b[1].minn;
59         for(int i=2;i<=cnt;i++)
60         {
61             if(now<=b[i].minn)
62             {
63                 ans=b[i].minn-sum;
64             }
65             now=b[i].maxx;
66             sum+=b[i].sum;
67         }
68 //        for(int i=1;i<=cnt;i++)
69 //        {
70 //            cout<<b[i].minn<<' '<<b[i].maxx<<' '<<endl;
71 //        }
72         cout<<ans<<endl;
73     }
74 }

正确代码;

#include <bits/stdc++.h>
using namespace std;
int a[100010];
struct node
{
    int minn;
    int maxx;
    int sum;
}b[100010];
int cnt;
bool cmp(node a,node b)
{
    return a.minn<b.minn;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cnt=0;
        int k;
        cin>>k;
        while(k--)
        {
            int n;
            cin>>n;
            cin>>a[1];
            int minn=a[1]+1;
            int now=a[1]+2;
            for(int i=2;i<=n;i++)
            {
                cin>>a[i];
            }
            for(int i=2;i<=n;i++)
            {
                //cin>>a[i];
                if(a[i]>=now)
                {
                    minn=max(a[i]-i+2,minn);
                    //cout<<minn<<endl;
                    now=a[i]+2;
                }
                else now++;
                //cout<<minn<<' '<<now<<endl; 
            }
            b[++cnt].minn=minn;
            b[cnt].maxx=now;
            b[cnt].sum=n;
            //cout<<b[cnt].minn<<' '<<b[cnt].maxx<<' '<<endl;
        }
        sort(b+1,b+1+cnt,cmp);
        int now=b[1].maxx;
        int sum=b[1].sum;
        int ans=b[1].minn;
        //cout<<ans<<endl;
        for(int i=2;i<=cnt;i++)
        {
            if(now<=b[i].minn)
            {
                ans=max(ans,b[i].minn-sum);
            }
            now=b[i].maxx;
            sum+=b[i].sum;
            //cout<<ans<<endl;
        }
//        for(int i=1;i<=cnt;i++)
//        {
//            cout<<b[i].minn<<' '<<b[i].maxx<<' '<<endl;
//        }
        cout<<ans<<endl;
    }
}

区别样例：

1 
22 11 16 12 12 16
1 6
4 19 1 15 22
10 24 11 6 7 11 15 20 22 2 6
10 5 3 6 1 12 24 20 4 1 23
6 10 3 24 1 24 8
1 19
7 8 23 4 5 7 20 18

这篇关于贪心局限性的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！