P1215 [USACO1.4] 母亲的牛奶 Mother's Milk 题解

NFOT · 2024-10-19 14:14:51 · 题解

原题

这道题我们只需要模拟倒牛奶的过程，并在 a=0 的时候将 c 的牛奶值记录就好。

模拟倒牛奶过程

到牛奶的方案有很多种，不妨使用 rand() 函数随机模拟。

loop:
int tmp=rand()%3+1;
int tmp1=rand()%3+1;
if(tmp==tmp1) goto loop;

两次随机确定牛奶从哪桶倒入哪桶，若两次随机结果一样，再重来就好了。

当 a=0 时记录 c 结果

使用高级的 vector 进行存储，每次记录结果时使用 find() 函数查找有没有重复，没有重复进行记录。

if(k[1]==0) if(find(v.begin(),v.end(),k[3])==v.end()) v.push_back(k[3]);//k[1],k[3]分别指a桶牛奶量与c桶牛奶量;

c 结果排序

将结果倒入到 int 数组进行 sort 排序

int res[500];
for(int i=0;i<v.size();i++) res[i]=v[i];
sort(res,res+v.size());
for(int i=0;i<v.size();i++) cout<<res[i]<<' '; 

附上 AC 全代码

#include<bits/stdc++.h>
using namespace std;
int m[5],k[5];
int main(){
    vector<int> v;
    srand(time(0));
    cin>>m[1]>>m[2]>>m[3];
    k[3]=m[3];
    for(int i=1;i<=20000000;i++){
        if(k[1]==0){
            if(find(v.begin(),v.end(),k[3])==v.end()) v.push_back(k[3]);
        }
        loop:
        int tmp=rand()%3+1;
        int tmp1=rand()%3+1;
        if(tmp==tmp1) goto loop;
        if(k[tmp]+k[tmp1]>m[tmp1]){
            k[tmp1]+=k[tmp];
            k[tmp]=k[tmp1]-m[tmp1];
            k[tmp1]-=k[tmp];
        }else{
            k[tmp1]+=k[tmp];
            k[tmp]=0;
        }
    }
    int res[500];
    for(int i=0;i<v.size();i++) res[i]=v[i];
    sort(res,res+v.size());
    for(int i=0;i<v.size();i++) cout<<res[i]<<' '; 
}