首页 > 试题广场 >

山寨金闪闪

[编程题]山寨金闪闪
  • 热度指数:3587 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
金闪闪死后,红A拿到了王之财宝,里面有n个武器,长度各不相同。红A发现,拿其中三件武器首尾相接,组成一个三角形,进行召唤仪式,就可以召唤出一个山寨金闪闪。(例如,三件武器长度为101520,可以召唤成功。若长度为101130,首尾相接无法组成三角形,召唤失败。)红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
博客内附带ac代码和完整思路,欢迎大家赏脸。
发表于 2019-07-14 15:12:14 回复(0)
#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)
#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)

在仔细阅读和思考了@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)
#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)
r-l+1为什么大于等于47就可以优化这么多??
发表于 2020-08-13 17:14:50 回复(3)
#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)
#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)