首页 > 试题广场 >

山寨金闪闪

[编程题]山寨金闪闪
  • 热度指数：3810 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
金闪闪死后，红A拿到了王之财宝，里面有n个武器，长度各不相同。红A发现，拿其中三件武器首尾相接，组成一个三角形，进行召唤仪式，就可以召唤出一个山寨金闪闪。（例如，三件武器长度为10、15、20，可以召唤成功。若长度为10、11、30，首尾相接无法组成三角形，召唤失败。）红A于是开了一个金闪闪专卖店。他把王之财宝排成一排，每个客人会随机抽取到一个区间[l,r],客人可以选取区间里的三件武器进行召唤（客人都很聪慧，如果能找出来合适的武器，一定不会放过）。召唤结束后，客人要把武器原样放回去。m个客人光顾以后，红A害怕过多的金闪闪愉悦太多男人，于是找到了你，希望你帮他统计出有多少山寨金闪闪被召唤出来。

数据范围： ， ，每件武器的长度满足

输入描述:
第一行武器数量:n <= 1*10^7
第二行空格分隔的n个int，表示每件武器的长度。
第三行顾客数量：m <= 1*10^6
后面m行，每行两个int l，r，表示每个客人被分配到的区间。（l
                        

                                                                

                        
输出描述:

                        
山寨金闪闪数量。

                                        
                                                                                            

                            
示例1

                            

                                

                                    
输入

                                    
5
1 10 100 95 101
4
1 3
2 4
2 5
3 5

                                

                                

                                    
输出

                                    
3
算法知识视频讲解
添加回答
koyume头像 koyume
博客内附带ac代码和完整思路，欢迎大家赏脸。
发表于 2019-07-14 15:12:14 回复(0)
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main()
{
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        int cnt=0;
        while(m--) 
        {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l+1>=47)
                cnt++;
            else if(r-l+1<3)
                continue;
            else {
                v.clear();
                for(int i=l; i<=r; i++)
                    v.push_back(a[i]);
                sort(v.begin(),v.end());
                int len=v.size();
                for(int i=0; i<len-2; i++) {
                    if(v[i]+v[i+1]>v[i+2]) {
                        cnt++;
                        break;
                    }
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

发表于 2019-08-14 21:12:04 回复(0)
Veitor头像 Veitor

在仔细阅读和思考了@koyume 的博客解题思路后，r-l+1>=47这个条件终于明白怎么得出的了。跟大家分享一下。

首先要把问题理解并转化成常规问题（去除无关干扰项）就是：从含有n个不同数字元素的数组中，取m个数组片段出来，则在这m个数组片段中，能有几个数组片段中的数字元素可以组成三角形？

接着我们对其中一个数组片段来研究

  1. 这种题的一般思路第一步都是先把这数组进行排序

  2. 第二步脑子里蹦出来的基本都是两种想法：

    1. 用三层循环暴力破解。
    2. 用三层循环暴力破解是绝对无法AC的。

所以第二步肯定得考虑其他方法，以这有序递增数组为例，要找出是否有构成三角形的三个数字，那就需要a+b>c（a<=b<=c）
而边界情况是a+b=c，三个边成了一条直线。

假设数组中任意三个相邻数字都会构成这个边界情况（实际上这一点是思路重点，但一般人谁想得出来啊，一般人最多只能想到边界情况，但很少会列出任意三个相邻数字构成边界的情况吧，所以这一点先硬背一下），则写出来就是1，1，2，3，5，8，13，31....这样的斐波那契数列

而题目中给了一个重要条件就是数组中每个数字是int类型，即最大为2^32-1=4294967295

所以把斐波那契数列一直列出到int类型最大值前后的话大概像这样（这个建议写个脚本列一下）：
1（第1项），1（第2项），2（第3项），3（第4项）.....1836311903（第46项），2971215073（第47项），（int最大值4294967295），4807526976（第48项）...

由此看出，第47项的数字是在int类型范围内的，而第48项在int类型范围之外。所以如果选取的数组片段中元素超过47个时，超出的数字必定落在上面47个边界数字的区间里，则必定能构成三角形。所以目前得出来条件应当是r-l+1>47，但注意题中数组中的数字都是唯一的，这里举例的斐波那契数列前两位都是1，稍微处理一下，所以最后应该是r-l+1>=47，能够省去大量的计算。

编辑于 2021-06-18 13:49:55 回复(0)
zymcc头像 zymcc 
#include<iostream>
#include<string>

using    namespace    std;

int main(){
    int n,m,n0=0;
    int q[10000000]={0};
    
    while(cin>>n){
        int jg=0;
        for(int i=0;i<n;i++){
            cin>>q[i];
        }
        cin>>m;
        int n1,n2;
        for(int i=0;i<m;i++){
            cin>>n1>>n2;
            n1--;
            
            if(n2-n1<3)
            {
                continue;
            }
            int  t=0;
            for(int j=n1;j<n2-2;j++){
                if(t==1){
                    break;
                }
                for(int k=j+1;k<n2-1;k++){
                    if(t==1){
                        break;
                    }
                    for(int l=k+1;l<n2;l++){
                        
                        if((q[j]+q[k]>q[l])){
                            if((q[j]+q[l]>q[k])){
                                if((q[k]+q[l]>q[j])){
                                    t=1;
                                    
                                    //cout<<q[j]<<","<<q[k]<<","<<q[l]<<";";
                                        break;
                                }
                            }
                        }
                    }
                }
            }
            jg=jg+t;
            
        }
        cout<<jg;
    }
}

发表于 2021-06-25 11:52:28 回复(0)
小润润头像 小润润 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        int cnt=0;
        while(m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l+1>=47)cnt++;//因为区间一旦很大就很容易构成三角形，别人测试出来的边界
            else if(r-l+1<3)continue;
            else {
                v.clear();
                for(int i=l; i<=r; i++)v.push_back(a[i]);
                sort(v.begin(),v.end());
                int len=v.size();
                bool flag=0;
                for(int i=0; i<len-2; i++) {
                    if(v[i]+v[i+1]>v[i+2]) {
                        flag=1;
                        break;
                    }
                }
                if(flag)cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        int cnt=0;
        while(m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l+1>=47)cnt++;//因为区间一旦很大就很容易构成三角形，别人测试出来的边界
            else if(r-l+1<3)continue;
            else {
                v.clear();
                for(int i=l; i<=r; i++)v.push_back(a[i]);
                sort(v.begin(),v.end());
                int len=v.size();
                bool flag=0;
                for(int i=0; i<len-2; i++) {
                    if(v[i]+v[i+1]>v[i+2]) {
                        flag=1;
                        break;
                    }
                }
                if(flag)cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        int cnt=0;
        while(m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l+1>=47)cnt++;//因为区间一旦很大就很容易构成三角形，别人测试出来的边界
            else if(r-l+1<3)continue;
            else {
                v.clear();
                for(int i=l; i<=r; i++)v.push_back(a[i]);
                sort(v.begin(),v.end());
                int len=v.size();
                bool flag=0;
                for(int i=0; i<len-2; i++) {
                    if(v[i]+v[i+1]>v[i+2]) {
                        flag=1;
                        break;
                    }
                }
                if(flag)cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main() {
    while(~scanf("%d",&n)) {
        for(int i=1; i<=n; i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        int cnt=0;
        while(m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l+1>=47)cnt++;//因为区间一旦很大就很容易构成三角形，别人测试出来的边界
            else if(r-l+1<3)continue;
            else {
                v.clear();
                for(int i=l; i<=r; i++)v.push_back(a[i]);
                sort(v.begin(),v.end());
                int len=v.size();
                bool flag=0;
                for(int i=0; i<len-2; i++) {
                    if(v[i]+v[i+1]>v[i+2]) {
                        flag=1;
                        break;
                    }
                }
                if(flag)cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}


发表于 2021-04-26 16:42:08 回复(0)
来个满意的offer吧！！！头像 来个满意的offer吧！！！
r-l+1为什么大于等于47就可以优化这么多？？
发表于 2020-08-13 17:14:50 回复(3)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m,cnt=0,l,r;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    cin>>m;
    while(m--){
        cin>>l>>r;
        if(r-l<2)
            continue;
        else if(r-l>=46)
            cnt++;
        else{
            vector<int> v;
            for(int i=l;i<=r;i++)
                v.push_back(a[i]);
            sort(v.begin(), v.end());
            for(int i=0;i<v.size()-2;i++)
                if(v[i]+v[i+1]>v[i+2]){
                    cnt++;
                    break;
                }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-10-08 01:24:27 回复(0)
不知名的小老弟头像 不知名的小老弟 
n=int(input())
f=[int(x) for x in input().split()]
m=int(input())
sum=0
for _ in range(m):
    lr=input().split()
    l=int(lr[0])-1
    r=int(lr[1])-1
    if(r-l+1>=47):
        sum+=1
    else:
        num=f[l:r+1]
        num.sort()
        for i in range(0,len(num)-2):
            if num[i]+num[i+1]>num[i+2]:
                sum+=1
                break
print(sum)


发表于 2019-08-19 16:44:40 回复(4)
NeeTeR头像 NeeTeR 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool hasChecked(const bool* check, const int& l, const int& r)
{
    if (!check[l - 1] && !check[r - 1])
    {
        for (int i = l; i < r - 1; ++i)
        {
            if (check[i])
            {
                return true;
            }
        }
    }
    return false;
}

bool calculate(const int* array, bool* check, const int& l, const int& r)
{
    for (int j0 = l - 1; j0 < r - 2; ++j0)
    {
        for (int j1 = j0 + 1; j1 < r - 1; ++j1)
        {
            for (int j2 = j1 + 1; j2 < r; ++j2)
            {
                if (array[j0] + array[j1] <= array[j2] || array[j0] + array[j2] <= array[j1] || array[j1] + array[j2] <= array[j0])
                {
                    continue;
                }
                else
                {
                    for (int k = j0 + 1; k < j2; ++k)
                    {
                        check[k] = true;
                    }
                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int n;
    scanf("%d", &n);
    int array[10000000] = { 0 };
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &array[i]);
    }
    bool check[10000000] = { false };
    int m;
    scanf("%d", &m);
    int result = 0;
    for (int i = 0; i < m; ++i)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        if (r - l < 2)
        {
            continue;
        }
        if (hasChecked(check, l, r))
        {
            ++result;
            continue;
        }
        if (calculate(array, check, l, r))
        {
            ++result;
            continue;
        }
    }
    printf("%d", result);

    return 0;
}

编辑于 2019-05-23 15:43:31 回复(4)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 哔哩哔哩 测试工程师 PHP工程师 复杂度 2019 数学 Java工程师
来自：哔哩哔哩 2019秋招...
上传者：小小
难度：
9条回答 9569浏览

热门推荐

通过挑战的用户

查看代码

相关试题

山寨金闪闪

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号