Acwing蓝桥杯省赛专题训练之贪心（相关真题和模板题）

题目：1055. 股票买卖 II

题解：贪心

#include 
using namespace std;
typedef long long LL;
typedef pair<int ,int > PII;
const int N=1e5+10;
int n;
int a[N];
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	LL sum=0;
	for(int i=1;i<n;i++){
		if(a[i]>a[i-1]) sum+=a[i]-a[i-1];
		
	}
	printf("%lld",sum);
	return 0;
}

题目：104. 货仓选址

题解：贪心，选中位数即可

#include 
using namespace std;
typedef long long LL;
typedef pair<int ,int > PII;
const int N=1e5+10;
int n;
int a[N];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	int t=(n+1)/2;
	LL sum=0;
	for(int i=1;i<=n;i++){
		sum+=abs(a[t]-a[i]);
	}
	printf("%lld",sum);
	return 0;
}

题目：122. 糖果传递

题解：中位数+贪心+数学推导

#include 
using namespace std;
typedef long long LL;
typedef pair<int ,int > PII;
const int N=1e6+10;
int n;
LL a[N];
int main(){
	cin>>n;
	LL sum=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	sum/=n;
	for(int i=1;i<=n;i++){
		a[i]=sum-a[i];
		a[i]+=a[i-1];
	}
	sort(a+1,a+1+n);
	LL ans=0;
	for(int i=1;i<=n;i++){
		ans+=abs(a[i]-a[(n+1)/2]);
	}
	printf("%lld",ans);
	return 0;
}

题目：112. 雷达设备

题解：贪心+数学

#include 
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=1e6+10;
int n,d;
PII a[1010];
int main(){
	cin>>n>>d;
	int x,y;
	bool flag=1;
	for(int i=0;i<n;i++){
		scanf("%d%d",&x,&y); 
		a[i].first=x+sqrt((double)d*d-y*y);
		a[i].second=x-sqrt((double)d*d-y*y);
		if(y>d) flag=0;
	}
	if(!flag){
		puts("-1");
	}else{
		sort(a,a+n);
		double r=-2000;
		int ans=0;
		for(int i=0;i<n;i++){
			if(r<a[i].second){
				ans++;
				r=a[i].first;
			}
		}
		printf("%d",ans);
	}
	return 0;
}

题目：1235. 付账问题

题解：贪心+均值不等式

#include 
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=5e5+10;
LL n,s;
int a[N];
int main(){
	cin>>n>>s;
	double AVG=s*1.0/n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+n);
	double avg=AVG,x=0;
	for(int i=1;i<=n;i++){
		if(a[i]<avg){
			s-=a[i];
			x+=(a[i]-AVG)*(a[i]-AVG);
			avg=s*1.0/(n-i);
		}else{
			s=0;
			x+=(avg-AVG)*(avg-AVG)*(n-i+1);
			break;
		}
	}
	x/=n;
	x=sqrt(x);
	printf("%.4f",x);
	return 0;
}

题目：1239. 乘积最大

题解：附上大佬解题思路

上图来源

#include 
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=1e5+10;
const int mod=1000000009;
int n,k;
LL a[N];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+1+n);
	LL sum=1;
	int sign=1;
	if(k%2){
		sum=(sum*a[n])%mod;
		if(a[n]<0) sign=-1;
		n--;
		k--;
	}
	int i=1,j=n;
	while(k){
		if(sign*a[i]*a[i+1]>sign*a[j]*a[j-1]){
			sum=((sum*a[i])%mod*a[i+1])%mod;
			i+=2;
		}else{
			sum=((sum*a[j])%mod*a[j-1])%mod;
			j-=2;
		}
		k-=2;
	}
	printf("%lld",sum);
	return 0;
}

题目：1247. 后缀表达式

题解：如果没有负号就是全部相加，如果有负号，就是加上最大的数，然后减去最小的数，中间剩余的都加上其绝对值

#include 
using namespace std;
typedef long long LL;
typedef pair<double ,double > PII;
const int N=2e5+10;
const int mod=1000000009;
int n,m;
int a[N];
int main(){
	cin>>n>>m;
	for(int i=0;i<n+m+1;i++)
		scanf("%d",&a[i]);
	sort(a,a+n+m+1);
	if(m==0){
		LL sum=0;
		for(int i=0;i<n+m+1;i++){
			sum+=a[i];
		}
		printf("%lld",sum); 
	}else{
		LL sum=0-a[0]+a[n+m];
		for(int i=1;i<n+m;i++){
			sum+=abs(a[i]);
		}
		printf("%lld",sum); 
	}
	return 0;
}

题目：1248. 灵能传输

题解：大佬题解

#include  
using namespace std;
typedef long long LL;
typedef pair<int ,int >PII;
const int N=3e5+10;
int t;
int n;
LL s[N],a[N];
int main() {
	cin>>t;
	while(t--){
		cin>>n;
		s[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%lld",&s[i]);
			s[i]+=s[i-1];
		}
		LL s0=0,sn=s[n];
		if(s0>sn){
			swap(s0,sn);
		}
		sort(s,s+n+1);
		for(int i=0;i<=n;i++){
			if(s0==s[i]){
				s0=i;
				break;
			}
			
		}
		for(int i=n;i>=0;i--){
			if(sn==s[i]){
				sn=i;
				break;
			}
		}
		bool sta[N];
		memset(sta,0,sizeof sta);
		int l=0,r=n;
		for(int i=s0;i>=0;i-=2){
			a[l++]=s[i];
			sta[i]=1;
		}
		for(int i=sn;i<=n;i+=2){
			a[r--]=s[i];
			sta[i]=1;
		}
		for(int i=0;i<=n;i++){
			if(!sta[i]){
				a[l++]=s[i];
			}
		}
		LL res=0;
		for(int i=1;i<=n;i++){
			res=max(res,abs(a[i]-a[i-1]));
		}
		printf("%lld\n",res);
	}
	return 0;
}