当前位置: 首页 > 工具软件 > Yogurt > 使用案例 >

POJ2393 Yogurt factory 贪心

程瑞
2023-12-01

题目链接
自己写的双重for循环找最小代价,结果TLE。。。。
其实只需要维护最小代价即可
TLE 代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX=0x3f3f3f3f;
const int N=10010;
struct Yogurt{
	int c,num,y;
}yogurt[N];
int dx[4]={0, -1, 0, 1};
int dy[4]={-1, 0, 1, 0};
bool cmp(Yogurt a,Yogurt b){
	return a.c<b.c;
}
int main(){
	int n,s,max_ans=-1;
	ll spend=0;
	scanf("%d%d",&n,&s);
	for(int i=0;i<n;i++){
		scanf("%d%d",&yogurt[i].c,&yogurt[i].y);
		yogurt[i].num=i;
	}
	sort(yogurt,yogurt+n,cmp);
	for(int i=0;i<n;i++){
		max_ans=-1;
		for(int j=0;j<i;j++){
			if(yogurt[i].c-yogurt[j].c>(yogurt[i].num-yogurt[j].num)*s){
				double ans=double(yogurt[i].c-yogurt[j].c)/(yogurt[i].num-yogurt[j].num);
				if(ans>max_ans){
					yogurt[j].y+=yogurt[i].y;
					spend+=(yogurt[i].num-yogurt[j].num)*s*yogurt[i].y;
					yogurt[i].y=0;
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		spend+=yogurt[i].c*yogurt[i].y;
	} 
	printf("%lld",spend);
} 

AC代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
using namespace std;
typedef long long ll;
const int MAX=0x3f3f3f3f;
const int N=10010;
int main(){
	int n,s,c,y,min_c=MAX;
	ll sum=0;
	scanf("%d%d",&n,&s);
	for(int i=0;i<n;i++){
		scanf("%d%d",&c,&y);
		min_c=min(min_c+s,c);
		sum+=min_c*y;
	}
	printf("%lld\n",sum);
}
 类似资料: