• Codeforce 8.15-8.22做题记录


    Chopping Carrots (Easy Version)-1700

    题意:给定长度为n的数组a,数组p长度为n且其中每个元素可在[1,k]间取整数。求 m a x i ⌊ a i / p i ⌋ − m i n i ⌊ a i / p i ⌋ max_i\lfloor a_i/p_i \rfloor - min_i\lfloor a_i/p_i \rfloor maxiai/piminiai/pi的最小值。
    数据范围 1 ≤ k , n ≤ 3000 1 \leq k,n \leq 3000 1k,n3000 1 ≤ a 1 ≤ a 2 ⋯ a n ≤ 3000 1 \leq a_1 \leq a_2 \cdots a_n \leq 3000 1a1a2an3000

    超时的思路:对每个i预处理能够达到的数。遍历每个i考察可以达到的数并假设其为最大值,对其他所有j!=i求最后一个小于等于该值的数。

    #include 
    using namespace std;
    typedef long long ll;
    const ll mod = 998244353;
    
    
    
    
    int main()
    {
        int t; cin>>t;
        for(int i  =0 ;i<t;i++)
        {
            int n,k;scanf("%d%d",&n,&k);
            int a[n];for(int  o = 0;o<n;o++)scanf("%d",&a[o]);
            if(k > a[n-1] || n == 1)printf("0\n");
            else
            {
                vector<int> m[n];
                for(int i = 0;i<n;i++) for(int j = k;j>=1;j--) if(m[i].size()==0||a[i]/j>m[i][m[i].size()-1])m[i].push_back(a[i]/j); 
                int ans = INT_MAX;
                for(int i = 0;i<n;i++)
                {
                    for(int v:m[i])
                    {
                        int maximal  = v;
                        int minmax = INT_MAX;
                        bool f  = true;
                        for(int j = 0;j<n;j++)
                        {
                           
                            if(i!=j)
                            {
                                auto iter = upper_bound(m[j].begin(),m[j].end(),v);      
                                iter = prev(iter);
                                if(iter-m[j].begin()>=0) minmax=min(minmax,*iter); else {f=false;break;}
                            }
                        }
                        if(f)ans = min(ans,maximal - minmax);
                    }
                }
                printf("%d\n",ans);
            }
        }
        system("pause");
        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

    原因分析:不必要的重复搜索。上述做法是遍历i,然后遍历每个v。但v的取值空间是十分有限的(最大值的取值),即使是在不同的i处,相同的v搜索结果完全一致。
    修改:直接枚举上述最大值v,其余做法相同。

    #include 
    using namespace std;
    typedef long long ll;
    const ll mod = 998244353;
    
    
    
    
    int main()
    {
        int t; cin>>t;
        for(int i  =0 ;i<t;i++)
        {
            int n,k;scanf("%d%d",&n,&k);
            int a[n];for(int  o = 0;o<n;o++)scanf("%d",&a[o]);
            if(k > a[n-1] || n == 1)printf("0\n");
            else
            {
                vector<int> m[n];
                for(int i = 0;i<n;i++) for(int j = k;j>=1;j--) if(m[i].size()==0||a[i]/j>m[i][m[i].size()-1])m[i].push_back(a[i]/j); 
                int ans = INT_MAX;
                for(int maximal = a[n-1]/k;maximal<=a[n-1];maximal++)
                {
                    int truemaximal = INT_MIN;
                    int minimum = INT_MAX;
                    bool f = true;
                    for(int j =  0;j<n;j++)
                    {
                        auto iter = upper_bound(m[j].begin(),m[j].end(),maximal);
                        iter = prev(iter);
                        if(iter-m[j].begin()>=0) {truemaximal = max(truemaximal,*iter);minimum=min(minimum,*iter);} else {f=false;break;}
                    }
                    if(truemaximal!=maximal) f=false;
                    if(f) {ans=min(ans,maximal - minimum);}
                }
                // cout<
                
                // for(int i = 0;i
                // {
                //     for(int v:m[i])
                //     {
                //         int maximal  = v;
                //         int minmax = INT_MAX;
                //         bool f  = true;
                //         for(int j = 0;j
                //         {
                           
                //             if(i!=j)
                //             {
                //                 auto iter = upper_bound(m[j].begin(),m[j].end(),v);      
                //                 iter = prev(iter);
                                
                //             }
                //         }
                //         if(f)ans = min(ans,maximal - minmax);
                //     }
                // }
                printf("%d\n",ans);
            }
        }
        system("pause");
        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
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66

    总结:注意如何才能避免不必要的重复搜索,可以与以前那道调和级数的题做对比。

  • 相关阅读:
    文件操作~
    8.python发送邮箱验证码——使用zmail发送邮件验证用户信息
    3d tiles规范boundingVolume属性学习
    基于Docker搭建单机版Kafka、RabbitMQ、Redis、RocketMQ、MySQL
    内插散点数据
    Datagrip:高效数据库管理和开发
    Python算法例7 四数乘积
    【看表情包学Linux】shell 命令及运行原理 | Linux 权限 | 文件权限的修改和转让 | 目录的权限 | Sticky bit 粘滞位
    Web前端:与Angular和React相比,为什么要选择Vue JS
    云原生 | Docker - [mysql 集群搭建]
  • 原文地址:https://blog.csdn.net/nth2000/article/details/126348043