贪心算法

例题

1、股票买卖

题目信息

思路

相邻两天，后>前，则交易一次

题解

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define maxsize 100010
using 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 <bits/stdc++.h>
#define int long long 
#define int long long 
#define maxsize 100010
using 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 <bits/stdc++.h>
#define int long long
#define endl '\n'
#define maxsize 1000100
using 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 <bits/stdc++.h>
#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;
}