【蓝桥杯】巧克力

问题描述：

题解分析：

错误思想：本来的想法是先使用低价格的巧克力，并且判断需要吃几块【其中内容比较细】，直接计算即可，但是本题好像不可以用简单的最小价格的贪心来做

正确思路：创建一个结构体存储每种巧克力的信息，创建一个set集合来存储哪一天未吃巧克力；

创建一个数组来存储多种巧克力的信息，并按照价格升序排序，价格相同，则按照保质期升序排序

如何安排小兰每天吃哪一款巧克力？

1.先吃最便宜的

2.但是问题是哪一天吃最便宜的？答案就是：邻接过期的哪一天吃

举例：假如一个巧克力A单价1、保质期3天，数量2，巧克力B单价2、保质期5，数量三；而小兰要

吃 8 天，那么优先安排小兰第3天吃A，第2天吃A，此时巧克力A已经吃完了；再安排吃巧克力B，

安排第5天吃B，第四天吃B，第一天吃B；就是这个思路

核心总结就是：先吃便宜的，在临过期的时间吃

解题代码：

贪心思路写的：不正确

错误出现在：局部最优不是全局最优

错误版本：（未全部通过）

//蓝桥国赛吃巧克力 
#include <bits/stdc++.h>
using namespace std;
int a[100050];
int b[100050];
int c[100050];
bool vis[100050];    //监督数组 
long long int pos = 0;   //当前可以吃的天数
long long int ans = 0;  //最后需要花费的价钱 
int x,n;
//筛选出价格最便宜的巧克力
int find(int* te,bool* tee)
{int maxx = 1e9+100;int T_i=0;for(int p=1;p<=n;++p){if(a[p]<maxx && tee[p]==false){maxx = a[p];T_i = p;}}return T_i;
} 
int main(){cin>>x>>n;for(int i=1;i<=n;++i){cin>>a[i]>>b[i]>>c[i];   //第 i 种巧克力的信息 }//从最简单的开始计算while(pos<x){//判断终止条件//1.找到最便宜的价格的下标int chept = find(a,vis);vis[chept] = true;int ts = b[chept] - pos;//2.判断当前最便宜的巧克力的天数是否满足已经过的天数if(ts>0){//开始判断剩余的天数 int mm = x - pos;if(ts > mm && c[chept]>mm){pos += mm;ans += mm*a[chept];break;}else if(ts > mm && c[chept]<mm){pos += c[chept];ans += c[chept]*a[chept];continue;}//说明还有可以买的//不用一下子买这么多---买几个这问题一定好好想清楚int ww = 1; if(ts<=c[chept]){pos += ts;ww = ts;}	else {pos += c[chept];ww = c[chept];}ans += (ww*a[chept]);}		}printf("%lld\\n",ans);//cout<<ans<<endl;	return 0;
}

AC版本：

一定要开 long long 来存储 ans 和 pos；

//蓝桥国赛吃巧克力 
#include <bits/stdc++.h>
using namespace std;
const int mmd = 1e5+100;
typedef long long ll;
typedef struct node{int a,b,c;bool operator<(node &jb){if(a == jb.a && b < jb.b)return b < jb.b;return a < jb.a;}
}node;
node md[mmd];
set<int> ms;   //存放未处理的日子 
int main(){int x,n;cin>>x>>n;for(int i=1;i<=n;++i){cin>>md[i].a>>md[i].b>>md[i].c;   //第 i 种巧克力的信息 }for(int i=1;i<=x;++i){ms.insert(i);}  //赋初值 //排序sort(md+1,md+1+n); //一个一个处理ll pos = 1;  //第一个巧克力 ll ans = 0;while(ms.size() && pos<=n)     //当有未处理的天数以及未处理完巧克力时 {while(md[pos].c && ms.size() && *ms.begin()<=md[pos].b)   //当前要处理的天数小小于保质期数 {ans += md[pos].a;md[pos].c--;//获取那个比保质期最近的那个时间auto it = ms.upper_bound(md[pos].b);    //第一个大于该数的it--;   //指向该数ms.erase(it); }pos++; }if(ms.size())cout<<-1<<endl;else cout<<ans<<endl;	return 0;
}