【分治】化装晚会

骑猪看日落 2022-06-10 23:41 176阅读 0赞

题目描述  
  
  
万圣节又到了！FJ打算带他的奶牛去参加化装晚会，但是，FJ只做了一套能容下两头总长不超过S (1≤S≤1000000)的奶牛恐怖服装。FJ养了N(2≤N≤20000)头按1--N顺序编号的奶牛，编号为i的奶牛的长度为L\_i(1≤L\_i≤1000000)。如果两头奶牛的总长度不超过S，那么她们就能穿下这套服装。  
FJ想知道，如果他想选择两头不同的奶牛来穿这套衣服，一共有多少种满足条件的方案。  
  
输入  
  
  
第1行是2个整数：N和S；  
第2～N+l行每行一个整数：L\_i。  
  
输出  
  
  
1个整数，表示FJ可选择的所有方案数。注意奶牛顺序不同的两种方案是被视为相同的。  
  
样例输入  
4 6  
3  
5  
2  
1  
  
  
样例输出  
4  
  
  
提示  
  
  
  
样例说明：4种选择分别为：奶牛1和奶牛3；奶牛l和奶牛4；奶牛2和奶牛4；奶牛3和奶牛4

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <map>
    #include <string>
    #include <stack>
    #define LL long long
    #define INF 0x7fffffff
    #define MAX 20005
    #define PI 3.1415926535897932
    #define E 2.718281828459045
    using namespace std;
    int n,s;
    int a[MAX];
    int main()
    {
    
        scanf("%d%d",&n,&s);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        int sum=0;
    
        for(int i=1;i<=n;i++)
        {
            int r=n,l=i;
             while (a[l]+a[r]>s && r>l)
             r--;
    
             sum+=(r-l);
        }
    
       printf("%d\n",sum);
    
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关分治算法

划分问题：整个问题划分成多个无关联的子问题。递归求解：递归调用求解各个子问题。合并问题：合并子问题的解，形成原始问题的解。 -------------------

港控/mmm°/ 2022年12月12日 04:58/ 0 赞/ 193 阅读

相关计算机学院的迎新晚会,计算机学院举办迎新晚会

9月24日晚，由计算机科学与技术学院团总支、学生会举办的2010计算机科学与技术学院迎新晚会在西区礼堂火爆上演。整台晚会创造性地打破了常规的框架，采用了颁奖典礼的形式将整场

谁践踏了优雅/ 2022年10月12日 14:53/ 0 赞/ 177 阅读

相关大湾区中秋晚会

朋友发我大湾区中秋晚会链接，看了几眼，感觉是为生于六十七十年代的人度身定做的，怀旧感十足，连我这种讨厌热闹几乎从不看春晚的无趣人物也忍不住看了一下。作为一个“不懂

待我称王封你为后i/ 2022年09月12日 06:46/ 0 赞/ 173 阅读

相关【分治】化装晚会

题目描述万圣节又到了！FJ打算带他的奶牛去参加化装晚会，但是，FJ只做了一套能容下两头总长不超过S (1≤S≤1000000)的奶牛恐怖服装。FJ养了N(2≤

骑猪看日落/ 2022年06月10日 23:41/ 0 赞/ 177 阅读

相关分治法

问题描述:假定一个已经排好顺序的一维数组,运用二分搜索算法,使得当前输入元素x不在数组中是，返回小于x的最大元素位置i和大于x的最小元素的位置j,当搜索元素在数组中，i 和j

怼烎@/ 2022年06月03日 05:52/ 0 赞/ 261 阅读

相关 3.15 晚会—「饿了么」之殇

一.开题有随想 3 月 15 号晚上的 315 晚会，相信很多人都记忆深刻，「饿了么」、「淘宝」等多家知名互联网厂商都被报出了负面的消息，BAT 中的百度也因为群众对其积

小咪咪/ 2022年02月01日 18:25/ 0 赞/ 261 阅读

相关分治法

Problem1一元三次方程的解题目描述有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三

╰半夏微凉°/ 2022年01月06日 22:11/ 0 赞/ 299 阅读

相关边分治

跟点分治差不多的东西，先转二叉，然后找边，分治。可以动态，还听说有个骚操作叫边分树合并... 注意虚点虚边的处理！注意边分治不能善终，\_n = 1的时候特判。 ![Con

野性酷女/ 2021年12月22日 16:49/ 0 赞/ 303 阅读

相关点分治

[传送门][Link 1]（洛谷） UPDATE:关于代码中时间复杂度的更正——在代码中每一次都要通过遍历一遍询问来得到答案，所以时间复杂度是O(NMlogN), !

- 日理万妓/ 2021年12月13日 05:04/ 0 赞/ 327 阅读

相关分治算法

可能我太菜了，众多题解的t0\t0 +t1\t2\2始终没看懂分治大模拟好！ include<bits/stdc++.h> using nam

妖狐艹你老母/ 2021年10月24日 00:20/ 0 赞/ 396 阅读