贪心算法专题
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
1.Acwing 1055. 股票买卖 II
思路逢涨就买
#include<iostream>
using namespace std;
int main()
{
int n;
long long ans=0;
int a[100005];
cin>>n;
cin>>a[0];
for(int i=1;i<n;++i)
{
cin>>a[i];
if(a[i]>a[i-1]) ans+=a[i]-a[i-1];
}
cout<<ans<<endl;
return 0;
}2.ACwing 104. 货仓选址
思路货仓一定在最中间的商店即货仓左端的商店数一定等于货仓右边的商店数
如果左右商店数不一样如左边有2个右边有4个
-------1--------2---------货仓-------3---------4---------5-----------6
那么货仓往左移动d个单位左边商店离货仓的总距离减少2d右边商店离货仓的总距离增加4d总距离增加2d。
同理可得若货仓向右移动d个单位总距离减少2d。
所以为了找到最佳选址货仓现在应该向右移动直到左右商店数都相等。
AC代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
long long ans=0;
long long a[100005];
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
}
sort(a+1,a+n+1);
int mid=(n+1)>>1;
for(int i=1;i<=n;++i)
{
ans+=abs(a[i]-a[mid]);
}
cout<<ans<<endl;
return 0;
}3.Acwing 122. 糖果传递
思路设最终每个小朋友最终得到M个糖果第n个小朋友给第1个小朋友x1个糖果第1个小朋友给第二个小朋友x2个糖果以此类推可以得到
AC代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1000005;
typedef long long ll;
int n;
int mid;
ll M=0,ans=0;
ll a[MAXN];
ll c[MAXN];
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
M+=a[i];
}
M/=n;
mid=(n+1)>>1;
for(int i=2;i<=n;++i)
{
c[i]=c[i-1]+M-a[i-1];
}
sort(c+1,c+n+1);
for(int i=1;i<=n;++i)
{
ans+=abs(c[i]-c[mid]);
}
cout<<ans<<endl;
return 0;
}4. Acwing112. 雷达设备
思路先算出每个小岛如果可以被覆盖的话雷达可以设立的区间。
再根据每个区间的右端点 从小到大排序每次选每段区间的右端点。
如果上次选择的右端点在这次的范围内则这次的小岛已经被上次的雷达覆盖不需再设雷达。
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 1005;
int x,y;
int n,d;
double len;
bool noAns;
double last = -1e20;
int ans=0;
struct Segment
{
double l,r;
bool operator<(const Segment a)const
{
return r<a.r;
}
}s[MAXN];
int main()
{
cin>>n>>d;
for(int i=0;i<n;++i)
{
cin>>x>>y;
if(y>d) noAns=true;
else
{
len=sqrt((double)d*d-y*y);
s[i]={x-len,x+len};
}
}
sort(s,s+n);
for(int i=0;i<n;++i)
{
if(last<s[i].l){
ans++;
last=s[i].r;
}
}
if(noAns) cout<<"-1"<<endl;
else cout<<ans<<endl;
return 0;
}5.Acwing 1235. 付账问题
评价老6数据最后一个测试点精度差0.0001
思路先将每个人的钱数从小到大排序如果这个人的钱低于平均值那么他就得All in同时后面的人也会因此付出更多的钱来弥补当钱多的人弥补的钱数都相等时方差最小。每次有人付不够钱都要更新 每个人应付钱数的平均值直到有人可以付清平均值的钱数也意味着后面的所有人也都能付清钱停止更新。
注意点选用long double 提高精度
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
const int MAXN = 500005;
int main()
{
int n;
int a[MAXN];
long double ans=0;
long double S;
long double tm,M;
cin>>n>>S;
for(int i=0;i<n;++i) cin>>a[i];
sort(a,a+n);
M=S/n;
tm=M;
for(int i=0;i<n;++i)
{
//tm=S/(n-i);
if(a[i]<tm)
{
ans+=(M-a[i])*(M-a[i]);
//S-=a[i];
tm+=(tm-a[i])/(n-i-1);
}
else
{
ans+=(M-tm)*(M-tm);
//S-=tm;
}
}
ans=sqrt(ans/n);
cout<<fixed<<setprecision(4)<<ans<<endl;
return 0;
}6.Acwing 1247. 后缀表达式
思路分类讨论
1.没有减号 那直接将所有数相加即可
2.有减号且数据有正有负。可以利用减号将任意个负数变为正数
一个负数 -a a为负数
多个负数-a+b+c abc为负数
3.有减号且数据都为正将一个整数减两遍可以让他还是整数但还必须减掉一个
例a-b-c-d= a + c + d -b
4有减号且数据都为负打头的数字一定是加必须加一个负数
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int n,m;
ll a[MAXN];
ll ans=0;
int main()
{
cin>>n>>m;
for(int i=0;i<n+m+1;++i) cin>>a[i];
sort(a,a+n+m+1);
if(m==0)
{
for(int i=0;i<=n;++i) ans+=a[i];
}
else
{
if(a[0]>0)
{
ans=-a[0];
for(int i=1;i<n+m+1;++i) ans+=a[i];
}
else if(a[n+m]<0)
{
ans=a[n+m];
for(int i=0;i<n+m;i++) ans+=abs(a[i]);
}
else
{
for(int i=0;i<n+m+1;++i) ans+=abs(a[i]);
}
}
cout<<ans<<endl;
return 0;
}