蓝桥杯 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;
}