P4087 [USACO17DEC]Milk Measurementc++代码
时间: 2023-07-16 20:11:42 浏览: 71
以下是P4087 [USACO17DEC]Milk Measurement的c++代码:
```c++
#include<bits/stdc++.h>
using namespace std;
int n,d,i,x,minn=1e9,maxn=-1e9,sum=7;//注意sum要初始化为7,因为一开始有三个人挤奶!
map<int,int> mp;
struct node{
int day,milk,id;//day表示某一天,milk表示这一天的产奶量,id表示这头牛的编号
}a[100010];
bool cmp(node x,node y){
return x.day<y.day;
}
int main(){
scanf("%d%d",&n,&d);
for(i=1;i<=n;i++){
scanf("%d%d%d",&a[i].day,&a[i].id,&a[i].milk);
minn=min(minn,a[i].id);//记录最小的牛的编号
maxn=max(maxn,a[i].id);//记录最大的牛的编号
}
sort(a+1,a+n+1,cmp);//排序
for(i=1;i<=n;i++){
int p=a[i].id;
mp[p]+=a[i].milk;//记录每头牛产奶总量
if(mp[p]-a[i].milk>=mp[minn]&&mp[p]>=mp[minn]){//如果这头牛的产奶总量减去这一天的产奶量后等于最小产奶量且这头牛的产奶总量大于等于最小产奶量
sum--;
}
if(mp[p]>=mp[maxn]&&mp[p]-a[i].milk<mp[maxn]){//如果这头牛的产奶总量大于等于最大产奶量且这头牛的产奶总量减去这一天的产奶量小于最大产奶量
sum++;
}
if(mp[p]-a[i].milk<mp[maxn]&&mp[p]>=mp[maxn]){//如果这头牛的产奶总量减去这一天的产奶量小于最大产奶量且这头牛的产奶总量大于等于最大产奶量
if(mp[maxn]-mp[p]+a[i].milk>0)sum++;
}
mp[p]-=a[i].milk;//减去这一天的产奶量
if(i==n||a[i].day!=a[i+1].day){//如果到了新的一天或者到了最后一天
if(mp[maxn]!=mp[a[i].id]&&mp[a[i].id]>=mp[maxn])sum++;//如果这头牛的产奶总量不等于最大产奶量且这头牛的产奶总量大于等于最大产奶量
if(mp[maxn]==mp[a[i].id]){//如果这头牛的产奶总量等于最大产奶量
if(a[i].id==maxn)sum+=0;//如果这头牛就是最大产奶量的牛,那么不需要增加计数器
else sum++;//否则需要增加计数器
}
if(mp[minn]!=mp[a[i].id]&&mp[a[i].id]>=mp[minn])sum++;//如果这头牛的产奶总量不等于最小产奶量且这头牛的产奶总量大于等于最小产奶量
if(mp[minn]==mp[a[i].id]){
if(a[i].id==minn)sum+=0;//如果这头牛就是最小产奶量的牛,那么不需要增加计数器
else sum++;//否则需要增加计数器
}
}
}
printf("%d\n",sum);
return 0;
}
```
该题的解题思路是模拟,需要注意细节问题。我们可以首先将输入的数据按天数排序,然后模拟每一天挤奶的情况,并根据题目要求进行计数即可。具体细节请见代码注释。