乱搞思路求hack

就是我考场时想出来一个贪心思路，就是先按奇排序，然后找出奇加偶最少的那种糖果，对于那些奇小于等于最少的奇加偶一半价格的都买一个，剩下的全买奇加偶最少的那种糖果。

然后写完代码发现大洋里WA on #6，我仔细研究了一下，发现是会多买奇，导致最后少买了一组奇加偶，于是我给贪心加了一个反悔的过程。

在前面买的时候就记录下最后买的是哪一种，最后算答案时先把一整组奇加偶的，剩下的先不判断能不能买最后的一个奇，而是去查询如果前面买过的那些不买是否能够多买一组。

成功过了样例 6，赛后我重写过了洛谷民间数据，求hack

CPP

123456789101112131415161718192021222324252627#include<bits/stdc++.h>
#define int long long
#define getchar_unlocked() getchar()
using namespace std;
inline int read() {int x=0,ff=1;char ch=getchar_unlocked();while(ch<48||ch>57) {if(ch==45)ff=-1;ch=getchar_unlocked();}while(ch>=48&&ch<=57) x=(x<<3)+(x<<1)+(ch^48),ch=getchar_unlocked();return x*ff;}
inline void write(int x,char ch){if(!x){putchar(48),putchar(ch);return;}if(x<0)putchar(45),x=-x;char a[20];int i=0;while(x)a[++i]=x%10+48,x/=10;for(;i;i--)putchar(a[i]);putchar(ch);}
const int N = 2e5 + 10;
int n,m,ans;struct A{int x,y;}a[N];
signed main() {
	n = read();m = read();int mn = 0,last = 0;
	for(int i=1;i<=n;i++)a[i] = {read(),read()};
	sort(a+1,a+1+n,[](A x,A y){return x.x<y.x;});
	for(int i=1;i<=n;i++)
		if(!mn||a[i].x+a[i].y<a[mn].x+a[mn].y||(a[i].x+a[i].y==a[mn].x+a[mn].y&&a[i].x>a[mn].y))
			mn = i;
	for(int i=1;i<=n;i++)if(i!=mn&&a[i].x<=m&&a[i].x<=(a[mn].x+a[mn].y)>>1){
		ans++;last = i;
		m -= a[i].x;
	}int x = m/(a[mn].x+a[mn].y);
	ans += x*2;m -= x*(a[mn].x+a[mn].y);
	for(int i=last;i;i--)if(i!=mn&&m+a[i].x>=(a[mn].x+a[mn].y)){
		m = m+a[i].x-a[mn].x-a[mn].y;
		ans++;
	}ans += m>=a[mn].x;
	cout<<ans;
	return 0;
}

讨论操作

回复

相关推荐

乱搞思路求hack