1. 首页
  2. 文章中心
  3. 牛客网

牛客寒假算法基础集训营2 (部分)

80 阅读 0 评论
我是靠谱客的博主 默默睫毛，最近开发中收集的这篇文章主要介绍牛客寒假算法基础集训营2 (部分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

处女座的签到题

链接：https://ac.nowcoder.com/acm/contest/327/A
来源：牛客网
 

题目描述

平面上有n个点，问：平面上所有三角形面积第k大的三角形的面积是多少?

输入描述:

第一行T，表示样例的个数。
对于每一组样例，第一行两个整数n和k，
接下来n行，每行两个整数x,y表示点的坐标
T<=80

3<=n<=100

-109<=x,y<=109

对于每一组样例，保证任意两点不重合，且能构成的三角形的个数不小于k

输出描述:

对于每一组样例，输出第k大三角形的面积，精确到小数点后两位（四舍五入）。

示例1

输入

复制

1
4 3
1 1
0 0
0 1
0 -1

输出

复制

0.50

说明

样例中一共能构成3个三角形，面积分别为0.5，0.5，和1，面积第3大的为0.5

题解 : 

          暴力枚举+ 向量的叉乘+nth_element();

向量乘参考: https://www.cnblogs.com/xiexinxinlove/p/3708147.html

利用向量积（叉积）计算三角形的面积和多边形的面积：

向量的数量积和向量积：

（1）  向量的数量积

 

（1）  向量的向量积

两个向量a和b的叉积（向量积）可以被定义为：

在这里θ表示两向量之间的角夹角（0° ≤ θ ≤ 180°），它位于这两个矢量 所定义的平面上。

向量积的模（长度）可以解释成以a和b为邻边的平行四边形的面积。求三角形ABC的面积，根据向量积的意义，得到：

a=axi+ayj+azk;

b=bxi+byj+bzk;

a×b=(aybz-azby)i+(azbx-axbz)j+(axby-aybx)k,为了帮助记忆，利用三阶行列式，写成：

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <vector>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
using namespace std ;
typedef long long LL;
const int MAX = 1005;
const int inf = 0xffffff;
const LL mod = 1e9+7 ;

int minn = 0x3f3f3f3f ;
int maxx = -0x3f3f3f3f;
// --------------------------------
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct Point{
	LL x ;
	LL y ;
};

int main()
{
	int T;
	Point a[MAX] ;
	cin >>T;
	while(T--){
		vector<LL> v ;
		int n , k ;
		scanf("%d%d",&n,&k);
		for(int i = 1 ; i<=n ; i++)
		{
			scanf("%lld%lld",&a[i].x,&a[i].y);
		}

		for(int i = 1 ; i<=n  ;i++)
		{
			for(int j = i+1 ; j<=n ; j++)
			{
				for(int k = j+1 ;k<=n;k++ )
				{
					LL area=abs((a[j].x-a[i].x)*(a[k].y-a[i].y)-(a[k].x-a[i].x)*(a[j].y-a[i].y))  ;
					v.push_back(area);
				}
			}
		}
		nth_element(v.begin(),v.begin()+v.size()-k,v.end()) ;
		LL ans = v[v.size()-k];
		if(ans %2 == 0 )
		{
			printf("%lld.00n",ans/2) ;
		}
		else
		{
			printf("%lld.50n",ans/2) ;
		}
	}
	
	


    return 0;
}

 

 

 

 

 

 

 

 

处女座的期末复习 (贪心)

链接：https://ac.nowcoder.com/acm/contest/327/J
来源：牛客网
 

题目描述

快要期末考试了，处女座现在有n门课程需要考试，每一门课程需要花ai小时进行复习，考试的起始时间为bi，处女座为了考试可以不吃饭不睡觉，处女座想知道他能否复习完所有的科目（即在每一门考试之前复习完该科目）。每一门课的考试时间都为两小时。

输入描述:

 

第一行一个整数n

第二行n个整数a1,a2,…,an,表示每门课需要复习的时间

第三行n个整数b1,b2,…,bn,表示每门课考试的时间

1<=n<=105

0<=ai<=109

0<=bi<=109

输出描述:

如果处女座能复习完，输出”YES”，否则输出”NO”

示例1

输入

复制

3
0 1 1
2 6 4

输出

复制

YES

说明

在0-1小时复习第2门课，
在1-2小时复习第3门课，
在2-4小时考第1门课，
在4-6小时考第3门课，
在6-8小时考第2门课

备注:

考试时不能复习，保证考试时间不会重叠。

复习可以拆开，只要复习时间够了即可。

题解 :

先对考试时间排序,  每次取复习的起始时间和 复习的这门课的所用的时间 和 考试的起始时间 作比较 ,如果 考试之前没时间复习这门课就输出 NO ,或者时间不够也输出 NO . 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
using namespace std ;
typedef long long LL;
const int MAX = 100005;
const int inf = 0xffffff;
const LL mod = 1e9+7 ;

int minn = 0x3f3f3f3f ;
int maxx = -0x3f3f3f3f;
// --------------------------------
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Point{
	int x ;
	int y ;
};
Point a[MAX] ;
bool cmp(const Point &a , const  Point &b)
{
	return a.y < b.y;
}
int main()
{

	int n ;
	cin >> n ;
	for(int i  = 1 ; i<=n ;i++ )
	{
		cin >> a[i].x ;
	}
	for(int i = 1 ; i<=n ;i++ )
	{
		cin >> a[i].y ;
	}
	
	sort(a+1,a+1+n,cmp);
	bool flag = true ;
	int sum = 0 ;
    Point t ;
	t.x = a[1].x ; // 复习第 i 门课的时间
	t.y = 0 ; // 复习第i 门课 起始时间 d
	for(int i = 1 ;i<=n ; i++ )
	{

		if(a[i].y > t.y + a[i].x)
		{
            // 如果第 i 门 课的起始时间 小于 复习的起始时间加 复习所用的时间
            // 更新起始时间 
			t.y +=a[i].x ;
		}
		else
		{
			flag = false ;
			break ;
		}
		
	}

	if(flag )
	cout<<"YES"<<endl;
	else
	cout<<"NO"<<endl;
    return 0;
}

 

 处女座的砝码

链接：https://ac.nowcoder.com/acm/contest/327/C
来源：牛客网
 

题目描述

处女座热爱做物理实验，为了实验，处女座必须要精确的知道物品的质量。处女座准备自己设计一套砝码，每一个砝码都是正整数，这套砝码必须能够精确测量出n以内所有正整数的质量，处女座想要知道至少需要多少个砝码。你可以在天平的任意一边放置砝码。

输入描述:

 

一行，一个正整数n

1<=n<=101000

输出描述:

一个整数，表示最少的砝码数。

示例1

输入

复制

20

输出

复制

4

说明

你可以选择1，2，6，11
1=1
2=2
3=1+2
4=6-2
5=6-1
6=6
7=6+1
8=6+2
9=6+2+1
10=11-1
11=11
12=11+1
13=11+2
14=11+2+1
15=11+6-2
16=11+6-1
17=11+6
18=11+6+1
19=11+6+2
20=11+6+2+1

题解(牛客): 

 也就是  

3^{ m } >= 2n+1

m = log3(2n+1)

m = left lfloor log(2n+1) /log (3)+1 right rfloor

 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
using namespace std ;
typedef long long LL;
const int MAX = 100005;
const int inf = 0xffffff;
const LL mod = 1e9+7 ;

int minn = 0x3f3f3f3f ;
int maxx = -0x3f3f3f3f;
// --------------------------------


int main()
{
	long double n , x = 1 , k = 1 ;
	cin >> n ;
	while(x<n)
	{
		x = 3*x +1 ;
		k++ ;
	}
	cout<<k ;


    return 0;
}

标程:


import math

n = int(input())

print(math.floor(math.log(2 * n - 1) / math.log(3)) + 1)

 

最后

以上就是默默睫毛为你收集整理的牛客寒假算法基础集训营2 (部分)的全部内容，希望文章能够帮你解决牛客寒假算法基础集训营2 (部分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(53)

相关文章

处女座的期末复习
处女座的期末复习
基础算法 —— 贪心算法【概述】【一般步骤】【例题】
基础算法 —— 贪心算法【概述】【一般步骤】【例题】
牛客寒假算法基础集训营2——J
牛客寒假算法基础集训营2——J
2J.处女座的期末复习（C++）处女座的期末复习（C++）
2J.处女座的期末复习（C++）处女座的期末复习（C++）
牛客寒假算法基础集训营2 (部分)
牛客寒假算法基础集训营2 (部分)
牛客寒假算法基础集训营2 J 处女座的期末复习
牛客寒假算法基础集训营2 J 处女座的期末复习
PMP-Project资源分配
PMP-Project资源分配
牛客寒假算法基础集训营2：处女座的期末复习（贪心入门）
牛客寒假算法基础集训营2：处女座的期末复习（贪心入门）

评论列表共有 0 条评论

立即
投稿
返回
顶部