蓝桥杯 Day6 贪心

贪心

1.要点

2.例题

2022 砍竹子

学习:
1.模拟砍竹子砍到高度1，不过要记录过程高度，以便后续判断是否存在(想到集合哈希),然后外面嵌套数组(活用数据结构)+resize给大小

vector<unordered_set<ll>> hs;//记录第i根竹子下降到1过程中的每一次高度
hs.resize(n+1);//resize保证大小 

2.整数默认向下取整，浮点数才用ceil()和floor(),
3.sqrtl对应long long

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=2e5+10;
vector<unordered_set<ll>> hs;//记录第i根竹子下降到1过程中的每一次高度 

ll chuli(ll x){
	return sqrtl(x/2+1);//sqrtl保证精度，整数默认向下取整 
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	hs.resize(n+1);//resize保证大小 
	ll res=0;
	for(int i=1;i<=n;i++){
		ll x;
		cin>>x;
		while(x>1){
			if(!hs[i-1].count(x))	res++;	//前一根竹子没有这个高度就加一次，前一根竹子有这个高度就不加，算前一根竹子处理，递推得出相同高度算处理一次 
			hs[i].insert(x);
			x=chuli(x);
		}
	}
	cout<<res;
	return 0;
}