首页 > 其他分享 >LevOJ P2081 矮人都城

LevOJ P2081 矮人都城

时间:2024-10-26 21:46:45浏览次数:3  
标签:底边 题目 骨头 矮人 等腰三角 长度 P2081 贪心 LevOJ

目录

1.题目

 1.1题目描述

1.2输入输出格式

1.3数据范围

1.4样例

2.算法标签(tag)

3.题解

3.1思路

3.2 AC代码


1.题目

 1.1题目描述

1.2输入输出格式

1.3数据范围

1.4样例

2.算法标签(tag)

贪心,构造,数学

3.题解

3.1思路

写这种题最关键的是什么?脑子要足够清晰!

我们需要构造的是等腰三角形,那么我们的前提就是必须要有一对长度相等的骨头,我们可以先计算每种骨头都有多少对,然后再看无法组对的骨头该如何使用。

如果我们拥有了一对长度为x的骨头,那么我们就需要一根长度在区间(0,2x)的骨头来作为底边。我们发现,x越小,越不容易找到符合条件的底边,而相对的,对于底边来说,骨头越长就越难与其他的腰构成三角形。

因此,我们就要从小到大枚举成对的腰,然后每次贪心地去找到可以组成三角形的无法配对的骨头中长度最长的那一根,这样就可以把条件苛刻的先用掉,最大地可能将所有孤立的骨头用到。

这样下来,可以组成三角形的骨头就只剩下成对的骨头之间了。在这种情况下,假如腰的长度是x,由于需要的底边是(0,2x),长度小于等于x的边必然可以与之构成等腰三角形,那么,我们就只需要贪心地从最长骨头开始找底边,不断将比他长度比他小的骨头拆出来,就一定可以构成等腰三角形,实现构造数量的最大化。最终构造出来的等腰三角形的个数便是:  (成对的骨头数量之和)/3。

3.2 AC代码

标签:底边,题目,骨头,矮人,等腰三角,长度,P2081,贪心,LevOJ
From: https://blog.csdn.net/2301_79921853/article/details/143259188

相关文章

  • LevOJ P2084奇迹树脂
    题目概述:给定了函数f的表达式与函数g的表达式,给了T(T<=100)次询问,每次询问一个数n(n<=1e12),求g(n)的值,最终答案对1e9+7取模。tag:记忆化,递归,数学题解:首先我们需要知道取模的常识:1.(a+b)%mod=(a%mod+b%mod)%mod2.a*b%mod=a%mod*b%mod3.(a+b)%mod=(a+b+mod)%mod......
  • LevOJ.sln - Beyond course 1
    LevOJ.sln-problemsB1682[Usaco2005Mar]OutofHay干草危机问题描述解决方法P1033简单排序问题描述解决方法法一冒泡排序#include<stdio.h>voidbubble_sort(intn,intarr[]){for(inti=0;i<n;i++){for(intj=0;j<n-i......
  • LevOJ平台 - 持续更新
    LevOJ平台题目可能的解决方法P1001a+b的问题题目描述解决方法#include<stdio.h>intmain(){inta,b;scanf("%d%d",&a,&b);printf("%d\n",a+b);return0;}P1031三角形的面积题目描述解决方法#include<stdio.h>#include<......
  • [lnsyoj3174/luoguP4823/TJOI2013]拯救小矮人
    题意给定序列\(a,b\)和常数\(h\),若序列中存在值\(k\)满足\(b_k+\sum_{i=1}^{\operatorname{len}(a)}a_i\geh\),则可将\(a_k,b_k\)删除,求从\(a\)中删除的数的数量最大为多少。sol由于\(b\)越小的数越靠后越难被删除,同时,\(a\)越大的数越可以帮助其他数字被删除,因......
  • NUIST Levoj P1220 皇后摆放问题
    #include<iostream>#include<algorithm>#include<vector>#include<cstring>usingnamespacestd;intchess[9][9];intarr[9][9];intcnt=0,sum=0;boolcheck(introw,intcol){ for(inti=1;i<9;i++)if(chess[i][col])returnfalse; for(inti=......
  • 并查集(nuist LevOJ P1648)
    一、并查集1.1并查集简介并查集是一种简单的集合表示,是一种树形数据结构,可处理不相交集合的合并及查询问题。并查集可求联动分支数。并查集存储:现有9个元素0~9,建立一个数组(初始化元素为-1),用数组下标表示元素,数组中的数据表示根节点的下标。数组中数据为负数时表示它是根节点......