贪心算法

贪心算法

• 例题
• • 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;}