首页 > 试题广场 > 山寨金闪闪
[编程题]山寨金闪闪

金闪闪死后,红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<r)


输出描述:
山寨金闪闪数量。
示例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)
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)