贪心题QwQ

做法

将狼按照2*t*s大小排序，从小到大取，即为最优

证明

设当前有两只狼a和b： 狼a花费时间ta，单位时间吃sa只羊 狼b花费时间tb，单位时间吃sb只羊

1. 先a后b (被吃掉羊的数量为suma)： suma = 2*ta*sb;

2. 先b后a (被吃掉羊的数量为sumb)： sumb = 2*tb*sa

为了让被吃掉的羊尽可能少，那就让2*t*s尽可能小，用sort排序即可

code

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

namespace syr
{
	const ll N = 1e5+10;
    struct node {
    	ll t;
    	ll s;
	}a[N];
	ll n, ans;
	ll s[N];
	bool cmp (node a, node b) {
		return a.t*b.s<b.t*a.s;
	}
	void work()
	{
		cin>>n;
		for (ll i=1; i<=n; i++) {
			cin>>a[i].t>>a[i].s;
			a[i].t *= 2;
		}
		sort(a+1, a+1+n, cmp);
		for (ll i=1; i<=n; i++)
			s[i] = s[i-1]+a[i].s;
		for (ll i=1; i<=n; i++)
			ans += a[i].t*(s[n]-s[i]);
		cout<<ans<<'\n';
	}
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

首先我们考虑如果只有两只狼的情况， $t_1,h_1,t_2,h_2$

那么如果我先送第一只会吃掉的羊是 $t_1\times h_2$，先送第二只会吃掉的羊是 $t_2\times h_1$

那么这样对于两个值比一下大小即可

那我们显然可以推广到 $n$ 个狼，然后根据这个排序，统计答案即可

代码比czp更加凝练

#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1e6+10;
int n,ans=0;
int sum[N];
struct node{
	int t,s;
}a[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
bool cmp(node a,node b){return a.t*b.s<b.t*a.s;}
signed main(){
//	freopen("B.in","r",stdin);
	n=reads();
	for(int i=1;i<=n;i++) a[i].t=reads()*2,a[i].s=reads();
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i].s;
	for(int i=1;i<=n;i++) ans+=a[i].t*(sum[n]-sum[i]);
	printf("%lld\n",ans);
	return 0;
}

邻项微扰法，强

对于狼a,狼b：

先接狼a，在时间2t~a~内，狼b会吃掉 2t~a~*s~b~只羊；

先接狼b，在时间2t~b~内，狼a会吃掉 2tb~*s~a~只羊；

对 2tasb 和 2tbsa 从小到大排序，贪心就完成了。

邻项微扰经验：国王游戏

题意

有n只狼

每只狼有两个属性

一个是要运走的时间t

一个是每个单位时间能吃的羊的数量s

做法

当t相等时，先送s大的更优

当s相等时，先送t小的更优

当s1>s2且t2>t1时，先送1更优

当s1>s2且t1>t2时，考虑贡献，如果先送1则产生贡献为2t1s2,否则贡献为2t2s1,所以我们要先送那个贡献大的，这样最后的答案会较小

friend bool operator < (node a,node b) {
		return a.t * b.s < a.s * b.t;
	}

code

记得开long long

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

inline long long R() {
	long long x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

inline void W(long long x) {
	if(x < 0) {
		putchar('-');
		x = -x;
	}
	if(x >= 10) W(x/10);
	putchar(x%10+'0');
}

const long long N = 1e5 + 10;

struct node {
	long long t, s;
	friend bool operator < (node a,node b) {
		return a.t * b.s < a.s * b.t;
	}
} a[N];

long long n, sum;

void read() {
	n = R();
	for(long long i = 1; i <= n; i++) {
		a[i].t = R();
		a[i].s = R();
		sum += a[i].s;
	}
}

void compute() {
	sort(a+1,a+1+n);
	long long ans = 0;
	for(long long i = 1; i <= n; i++) {
		sum -= a[i].s;
		ans += 2 * a[i].t * sum;
	}
	W(ans);
	putchar('\n');
}

void run() {
	read();
	compute();
}

int main() {
	run();
	return 0;
}