求调玄关，马蜂良好USACO题目

题目描述农场主约翰以其农场生产的牛奶质量闻名遐迩，他正在为他的N个最好的朋友(1≤N≤50)举办一场牛奶品鉴会。不幸的是，派对上出现的M种牛奶(1≤M≤50)中，有一种已经变质，但农夫John不知道是哪一种!任何人喝了变质的牛奶都会生病，无论是在晚会的剩余时间还是之后。

你会收到一份派对记录——谁在什么时候喝奶，谁在什么时候生病。根据这些信息，你可以推断出哪一种牛奶可能是坏的。利用这一知识，帮助农民约翰确定他将需要准备的最低剂量的药物，以确保他能治愈所有生病的人，无论是在聚会期间或之后。

输入输入的第一行包含整数N、M、D和S。

接下来的D行(1≤D≤1000)每一行包含三个整数p,m,t，表示p在t时刻喝了牛奶m, p的值在1…N范围内，m在1…M范围内，t在1…100范围内。一个人可以多次喝同一种牛奶，也可以在同一时间点喝好几种类型的牛奶。

接下来的S行(1≤S≤N)每一行包含两个整数p,t，表示人p在t时刻患病，p的值在1…N范围内，t在1…100范围内。每个人最多会生病一次，而他们之所以会生病，只是因为他们在严格意义上更早的某个时间点喝了变质的牛奶。

输出一个单一的整数，表示农民约翰需要准备的最小剂量，这样他就可以保证他将有足够多的剂量来治疗所有生病的人，无论是在聚会期间还是之后。

样例输入 3 4 7 2 1 1 1 1 4 1 1 3 4 1 2 2 3 1 3 2 1 5 2 2 7 1 3 2 8 样例输出 3 提示有3个人和4种类型的牛奶。1号在时间3生病，2号在时间8生病。3号在聚会上没有生病，尽管如此，我们仍然需要考虑他在聚会结束后生病的可能性。让我们一个一个地考虑牛奶的种类，看看哪些会变质；我们知道，如果每个患病的人在患病前都喝这种类型的牛奶，那么这种类型的牛奶可能是有害的。

牛奶1:两个病人(1和2)在生病前都喝了这种牛奶，所以这可能是坏牛奶。如果是这样的话，3也喝了，所以一共会导致3个人生病(3会在聚会后生病)。

牛奶2:两个生病的人在生病前都喝了这种牛奶，所以这也可能是坏牛奶。没有其他人喝这种牛奶，所以最坏情况下，如果这是坏牛奶，总共有两个人会生病。

牛奶3:这不可能是坏牛奶，因为1号人在生病前没有喝——1号在时间4喝了牛奶3，但是1号是在时间3生病的，如果牛奶3与1号患病有关，那么1号最迟需要在时间2之前喝。

牛奶4:这不可能是坏牛奶，因为2号没有喝，但2号生病了。

因此，答案是农民约翰必须获得3剂药，因为如果牛奶1是坏的，那么总共需要3个人被治愈。

CPP

#include<bits/stdc++.h>
using namespace std;
struct find{
	int p,m,t;
}a[105];
struct ff{
	int p2,m2,t2;
}b[105];
bool pan[205];
int n,m,d,s;
int ans=0;
int ans2=-0x3f3f3f;
int main(){
	cin>>n>>m>>d>>s;
	for(int i=1;i<=n;i++){
		cin>>a[i].p>>a[i].m>>a[i].t;
	}
	for(int i=1;i<=m;i++){
		cin>>b[i].p2>>b[i].m2>>b[i].t2;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(b[j].p2==a[i].p&&a[i].t<=b[j].t2){
				pan[j]=true;
			}
//			else{
//				pan[j]=false;
//			}
		}
	}
	for(int i=1;i<=m;i++){
//		cout<<1;
	
		if(pan[i]==true){
//			cout<<1;
			for(int j=1;j<=n;j++){
				if(a[j].p==b[i].p2){
//					cout<<2;
					ans++;
				}
			}
		}
		ans2=max(ans2,ans);
	}
	cout<<ans2;
}

求调玄关，马蜂良好USACO题目

讨论操作

回复

相关推荐

求调玄关，马蜂良好USACO题目