题目链接
自己写的双重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);
}