贪心算法
- 例题
- 1、股票买卖
- 题目信息
- 思路
- 题解
- 2、货仓选址
- 题目信息
- 思路
- 题解
- 3、糖果传递
- 题目信息
- 思路
- 题解
- 4、雷达设备
- 题目信息
- 思路
- 题解
例题
1、股票买卖
题目信息
思路
相邻两天,后>前,则交易一次
题解
#include #define endl '\n'#define int long long#define maxsize 100010using namespace std;int n;int money[maxsize];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;int sum=0;for(int i=0;i<n;i++){cin>>money[i];}for(int i=0;i<n-1;i++){int cha=money[i+1]-money[i];if(cha >0){sum+=cha;}}cout<<sum<<endl;return 0;}
2、货仓选址
题目信息
思路
题解
#include #define int long long #define int long long #define maxsize 100010using namespace std;int n;int num[maxsize];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=0;i<n;i++){cin>>num[i];}sort(num,num+n);int c=num[(n-1)/2];int sum=0;for(int i=0;i<n;i++){sum +=abs(num[i]-c);}cout<<sum<<endl;return 0;}
3、糖果传递
题目信息
思路
题解
#include #define int long long#define endl '\n'#define maxsize 1000100using namespace std;int n;int average;int a[maxsize],c[maxsize];signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int sum=0;int count=0;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) sum+=a[i];average=sum/n;for(int i=1;i<=n;i++){c[i]=c[i-1]+average-a[i];}sort(c+1,c+n+1);int xn=c[(1+n)/2];for(int i=1;i<=n;i++) count +=abs(c[i]-xn);cout<<count<<endl;return 0;}
4、雷达设备
题目信息
思路
题解
#include #define int long long#define maxsize 1010#define endl '\n'using namespace std;struct node{double l;double r;}qujian[maxsize];bool judge(node a,node b){return a.r<b.r;}int n,d;signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int x,y;int count=0;bool fail=false;cin>>n>>d;for(int i=0;i<n;i++){cin>>x>>y;if(d<y) fail=true;else{double len=sqrt(d*d-y*y);qujian[i].l=x-len;qujian[i].r=x+len;}}if(fail) cout<<"-1"<<endl;else{sort(qujian,qujian+n,judge);double jilu=qujian[0].r;count=1;for(int i=1;i<n;i++){if(jilu<qujian[i].l){count++;jilu=qujian[i].r;}}cout<<count<<endl;}return 0;}