山寨金闪闪

C++ 解法, 执行用时: 125ms, 内存消耗: 23868KB, 提交时间: 2021-08-18

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 20000000
#define INF 1e9+7

using namespace std;

inline int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c > '9' || c < '0') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + ( c ^ 48); c = getchar();}
    return f * x;
}

int a[10000005], n, m, b[50];

signed main()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    int m = read(), ans = 0;
    while (m--)
    {
        int l = read(), r = read(), num = r - l + 1;
        if (r - l <= 1) continue;
        if (r - l + 1 >= 47) {ans++; continue;}
        for (int i = l; i <= r; i++) b[i - l + 1] = a[i];
        sort(b + 1, b + num + 1);
        for (int i = 1; i + 2 <= num; i++)
            if (b[i] + b[i + 1] > b[i + 2])
            {
                ans++;
                break;
            }
    }
    cout << ans;
    return 0;
}

C++ 解法, 执行用时: 252ms, 内存消耗: 4208KB, 提交时间: 2021-09-06

#include <bits/stdc++.h>
using namespace std;

int f[10'000'007];
int main() {
    int n, m, l, r, res = 0, g[47];
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &f[i]);
    }
    scanf("%d", &m);
    for (; m; m --) {
        scanf("%d %d", &l, &r);
        int len = r - l + 1;
        if (len < 3) continue;
        else if (len > 40) { ++res; continue; }
        memcpy(g, f + l, len << 2);
        sort(g, g + len);
        for (int i = 2; i < len; ++i) {
            if (g[i - 2] + g[i - 1] > g[i]) {
                ++res;
                break;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

C++ 解法, 执行用时: 277ms, 内存消耗: 4344KB, 提交时间: 2021-10-12

/*
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> length;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        length.push_back(tmp);
    }
    
    int m;
    cin >> m;
    
    int result = 0;
    for(int i = 0; i < m; i++)
    {
        int l, r;
        cin >> l >> r;
        
        if(r - l < 2) continue;
        if(r - l + 1 >= 47)
        {
            result++;
            continue;
        }
        
        vector<int> choose;
        for(int j = l; j <= r; j++)
        {
            choose.push_back(length[j]);
        }
        sort(choose.begin(), choose.end());
        
        for(int j = 0; j < choose.size() - 2; j++)
        {
            if(choose[j] + choose[j + 1] > choose[j + 2])
            {
                result++;
                break;
            }
        }
    }
    
    cout << result;
    
    return 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;
}

C++ 解法, 执行用时: 316ms, 内存消耗: 4220KB, 提交时间: 2022-03-16

#include<bits/stdc++.h>
using namespace std;
const int MAXN=(int)1e7 + 5;
int n,a[MAXN],m;
vector<int>v;
int main()
{
    int cnt = 0;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    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-1; 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;
}

C++ 解法, 执行用时: 347ms, 内存消耗: 4208KB, 提交时间: 2022-04-25

// //n个武器
// #include <iostream>
// #include <cstring>
// #include <cmath>
// #include <algorithm>
// using namespace std;
// typedef long long ll;
// int main() {
//     ll n;
//     cin >> n;
//     ll a[n];
//     for (ll i = 0; i < n; i++)
//         cin >> a[i];
//     ll m;//顾客数
//     cin >> m;
//     ll num = 0; //可召唤的个数
//     for (ll i = 0; i < m; i++) {
//         ll len[n];

//         //for(ll i=0;i<n;i++)
//         //len[i]=a[i];//复杂度太大
//         memcpy(len, a, sizeof(a));

//         ll a, b;
//         cin >> a >> b; //客人被分配到的区间
//         //构成三角形的要求：两边之和（较小的两边）大于第三边，两边只差(最大值-最小值小于第三边
//         //两边之和大于第三边等价于两边之差小于第三边
//         if (b - a < 2) { //可取的元素个数为b-a+1,范围从a-1到b-1
//             num += 0;
//             continue;
//         }
//         ll t = b - a + 1;
//         ll max_ele1 = *max_element(len + a - 1, len + b); //?
//         ll max_index1 = max_element(len + a - 1, len + b) - len;
//         len[max_index1] = 0;
//         ll max_ele2 = *max_element(len + a - 1, len + b); //?
//         ll max_index2 = max_element(len + a - 1, len + b) - len;
//         len[max_index2] = 0;
//         ll max_ele3 = *max_element(len + a - 1, len + b); //?
//         ll max_index3 = max_element(len + a - 1, len + b) - len;
//         len[max_index3] = 0;
//         t = t - 3;
//         while (t > -1) {
//             //cout<<max_ele1<<" "<<max_ele2<<" "<<max_ele3<<endl;
//             if (max_ele3 + max_ele2 > max_ele1) {
//                 num += 1; //满足三角形
//                 break;
//             }
//             //不满足
//             max_ele1 = max_ele2;
//             max_ele2 = max_ele3;
//             //重新获取max_ele3,剩下
//             max_ele3 = *max_element(len + a - 1, len + b); //?
//             max_index3 = max_element(len + a - 1, len + b) - len;
//             len[max_index3] = 0;
//             t--;
//         }
//         //cout<<num<<endl;

//     }
//     cout << num << endl;
//     return 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();
                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;
}

详情