备考CSP-J—贪心-Toy模板网

这篇具有很好参考价值的文章主要介绍了备考CSP-J—贪心。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

额……既然是备考，那么一定要动脑筋，一共5题，大家好好思考一下。

一：P1250 种树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

二：P1020 [NOIP1999 提高组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

三：P1230 智力大冲浪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

四：P1095 [NOIP2007 普及组] 守望者的逃离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

五：

某天 KID 利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID 虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为 w 的物品。岛上金属有 s 个种类, 每种金属重量不同，分别为 n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为 v1,v2,...,vs。KID 想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比

思考一小时……

一

思路：贪心。要让树最少，就要让树种在区间的重叠部分。所以，将尾部从小到大排序；遍历每一个区间，用一个变量表示这个区间已经种了多少棵树，若未达到意见，则从后往前种。

#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
struct tree{
	int x,y,t;
}s[509];
bool used[10000];
bool cmp(tree a,tree b){
	return a.y<b.y;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>s[i].x>>s[i].y>>s[i].t;
	}
	sort(s+1,s+1+m,cmp);
	for(int i=1;i<=m;i++){
		int k=0;
		for(int j=s[i].x;j<=s[i].y;j++) if(used[j]) k++;
		if(k>=s[i].t) continue;
		for(int j=s[i].y;j>=s[i].x;j--){
			if(used[j]==0){
				k++;
				ans++;
				used[j]=1;
				if(k>=s[i].t) break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

三

思路：先挑扣款大的玩，如果时间被占用了，就只能扣钱了。

#include <bits/stdc++.h>
using namespace std;
int m,n,used[509],ans;
struct game{
	int t,w;
}s[509];
bool cmp(game a,game b){
	return a.w>b.w;
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>s[i].t;
	for(int i=1;i<=n;i++) cin>>s[i].w;
	ans=m;
	sort(s+1,s+1+n,cmp);
	for(int i=1;i<=n;i++){
		int time=s[i].t;
		while(time>0&&used[time]) time--;
		if(time>0) used[time]=true;
		else ans-=s[i].w;
	}
	cout<<ans<<endl;
	return 0;
}

四

思路：能闪烁就闪烁，魔法值不够就加。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,s,t,now=0;
    cin>>m>>s>>t;
    int s1=0,s2=0;
    for(int i=1;i<=t;i++)
    {
        s1+=17;
        if(m>=10) {s2+=60;m-=10;}
        else m+=4;
        if(s2>s1) s1=s2;
        if(s1>s){
            cout<<"Yes"<<endl<<i<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl<<s1<<endl;
    return 0;
}

五

思路：算一算性价比文章来源地址https://www.toymoban.com/news/detail-824669.html

#include<bits/stdc++.h>
using namespace std;
struct gold{
    int n,v; double dj;
} a[109];
int k,s,w;double ans_v; 
int cmp(gold x,gold y) 
{ return x.dj>y.dj;}
int main()
{   cin>>k;
    while(k--)
    {
        cin>>w>>s;
        ans_v=0; 
        for(int i=1;i<=s;i++)
        {
            cin>>a[i].n>>a[i].v;
            a[i].dj=a[i].v*1.0/a[i].n;
        }
        sort(a+1,a+1+s,cmp);
        int j=1;
        while(w>0&&j<=s)
        {
            if(a[j].n<w) { ans_v+=a[j].v;w-=a[j].n;}
            else { ans_v+=w*a[j].dj;w=0;}
            j++;
        }
        printf("%.2f\n",ans_v);
     } 
    return 0;
 }

到了这里，关于备考CSP-J—贪心的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！