Java教程

贪心问题

本文主要是介绍贪心问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

T1：奶牛晒衣服

加工生产调度

emmm写他的时候突然想起来学长带着做题时有一个什么产工件的题，其中有一个题解用洗衣机和烘干机模拟 A B 工程。那时候我以为作者大抵是闲的，现在看到此题才明白过来

另外复习一下优先队列

priority_queue<int> a;//默认小根（大顶）
priority_queue<int, vector<int>, less<int> > a;   //同上
priority_queue<int, vector<int>, greater<int> > c;//这样就是大根（小顶）
查看代码 
#include<bits/stdc++.h>
using namespace std;
int n,a,b;
priority_queue<int> c;
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=0,j;i<n;i++)
    {
        scanf("%d",&j);
        c.push(j);
    }
    int t=0;
    while(c.top()>a*t)
    {
        int now=c.top();
        c.pop();
        t++;
        c.push(now-b);
    }
    printf("%d\n",t);
    return 0;
}

 T2：雷达装置

查看代码 
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
double d,x[10002],y[10002],temp;
struct node{
	double l,r;
}a[10002];
double cmp(node w,node e){
	return w.r<e.r;
}
int main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
		if(y[i]>d){
			cout<<"-1"<<endl;
			return 0;
		}
		a[i].l=x[i]-sqrt(d*d-y[i]*y[i]);
		a[i].r=x[i]+sqrt(d*d-y[i]*y[i]);
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(i==1) temp=a[i].r,ans++;
		else if(temp>a[i].l) continue;
		else temp=a[i].r,ans++;
	}
	cout<<ans<<endl;
	return 0;
}

T3：畜栏预定

查看代码 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans[600000],num;
struct node
{
	int s,p;
}a[100001],b[100001];
int cmp(node x,node y)
{
	return x.s<y.s;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].s,&b[i].s);
		a[i].p=b[i].p=i;
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	int j=1;
	for(int i=1;i<=n;i++)
	{
		if(j<=n)j++;
		if(!ans[b[i].p])ans[b[i].p]=++num;
		while(a[j].s<=b[i].s&&j<=n)j++;
		ans[a[j].p]=ans[b[i].p];
	}
	printf("%d\n",num);
	for(int i=1;i<=n;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

T4：荷马史诗

查看代码 
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct node {
	LL x,v;
	bool operator < (const node &aa) const {
		return x>aa.x || (x==aa.x && v>aa.v);
	}
};
priority_queue<node> q;
int n,m;
int main() {
	LL x;
	scanf("%d%d",&n,&m);
	for (int i=1; i<=n; i++) {
		scanf("%lld",&x);
		q.push((node) {
			x,0
		});
	}
	while ((n-1)%(m-1)!=0) {
		++n;
		q.push((node) {
			0LL,0
		});
	}
	LL ans=0;
	while (q.size()>1) {
		LL sum=0,d=0;
		for (int i=1; i<=m; i++)
			if (!q.empty()) {
				node now=q.top();
				q.pop();
				sum+=now.x;
				if (now.v>d) d=now.v;
			}
		ans+=sum;
		q.push((node) {
			sum,++d
		});
	}
	cout<<ans<<endl<<q.top().v;
	return 0;
}
这篇关于贪心问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航