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