用暴力写贪心

写了依托的贪心

csps T1 的解法多数用了贪心或者求众数，我也一样用了贪心，但是用了结构体，还设了另一个数组来统计，设了个变量来维护，结果打完之后和其他选手讨论 T1 的时候其他选手一脸匪夷所思：这玩意需要用到这个吗？

最后令人忍俊不禁的是，CCF只给它评了 35 分，然而这个代码经过自测是可以 AC 的，要不是复活赛过了真想把 CCF 骂一顿（不对，我 csps 的奖没了，确实该骂）

后面我又去做了些贪心题，发现这种维护思想虽然不是最优解，但是好写，写起来思路也很清晰，个人认为是个不错的做贪心题目的方法。

参考题目

P9121 [USACO23FEB] Hungry Cow B

从后往前减，如果不满足干草要求就只加干草数，否则加天数之和，最后一天因为有天数重合，所以额外加 1。

代码如下：

CPP

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define str string
#define db double

//判断每天是否有干草，有则加 1。 

ll n,t;
ll ans=0;
ll d[200000],b[200000];

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>d[i]>>b[i];
	}
	ll cnt=0;
	for(int i=2;i<=n+1;i++){
		if(i==n+1){
			if(t-d[i-1]>=b[i-1]+cnt) ans+=b[i-1]+cnt;
			else ans+=t-d[i-1]+1;
		}
		else{
			if(d[i]-d[i-1]>=b[i-1]+cnt) ans+=b[i-1]+cnt,cnt=0;
			else ans+=d[i]-d[i-1],cnt+=b[i-1]-(d[i]-d[i-1]);
		}
	}
	cout<<ans;
	return 0;
}

这样一来，T1 duel 也可以这样解决，先排序，然后统计数量，往前减，多余的就保留记录多出来的放到下次一起减，少的就照例减，打完后统计每个攻击力的怪兽，最后一起相加即可。

题目 P11231 [CSP-S 2024] 决斗

考场写的代码，这里的注释也是我在考场上写的：

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long

// 5
// 1 2 3 1 2
// 3 2 2 1 1
// 2消灭1，3消灭2
// 因此，将攻击力排序，然后令第二小的数减去第一小的数即可
// 桶排序，将攻击力从小到大排序，从后往前减
// 那么问题来了，怎么去设这个贪心？( 
// 5 4 3 2 1        1
// 3 3 3 2 2 1 1    3
// 2 1 1 1 1 1 1    6
// 4 3 3 2 2 2 1    3
// 将小数组减去大数组，剩下的全部相加即可。 

ll n;
ll r;
ll ans=0;
struct node{
	ll s,num;
}a[100050];
bool cmp(node a,node b){
	return a.num>b.num;
}
ll b[100050];
int main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	ll p;
	for(int i=1;i<=n;i++){
		cin>>r;
		a[r].s++;
		a[r].num=r;
	}
	sort(a+1,a+1+100000,cmp);
	b[1]=a[1].s;
	for(int i=2;i<=n;i++){
		if(a[i].s){
			if(a[i].s<a[i-1].s+p) p+=a[i-1].s-a[i].s,b[i]=0;
			else b[i]=a[i].s-a[i-1].s-p,p=0;
		}
	}
	for(int i=1;i<=n;i++){
		ans+=b[i];
	}
	cout<<ans;
	return 0;
}

因此实际上写这玩意跟暴力没啥区别（

还是不理解只给 35 分是为什么，~~甚至不知道怎么水测试点能把这题水到 35 分，太奇怪了~~

文章操作

写了依托的贪心

参考题目

相关推荐

评论

用暴力写贪心