P3275 [SCOI2011] 糖果 题解

P3275 [SCOI2011] 糖果

Description

给你 \(k\) 个指令（约束条件），让你构造一个长度为 \(n\) 的正整数序列 A，满足这个条件的同时让所有元素的和最小。

指令的格式如下：

• 1 a b 表示 \(A_a=A_b\)
• 2 a b 表示 \(A_a<A_b\)
• 3 a b 表示 \(A_a\ge A_b\)
• 4 a b 表示 \(A_a>A_b\)
• 5 a b 表示 \(A_a\le A_b\)

\(1\le n,k\le 10^5\)

Solution

考虑贪心。

可以根据每个指令来最小化地更新 \(A\)。我们试图让每个元素都最小。当有一个操作时，我们可以把不满足条件的值修改成满足条件的最小值。

\(A\) 是正整数序列，所以我们考虑把 \(A\) 中的值全部初始化为 \(1\)。

这样的话，每次修改后的值是单调不降的，因而保证了答案的正确性。

具体地：

• 1 a b 时，\(A_{a}=A_{b}=\max(A_a,A_b)\)
• 2 a b 时， \(A_b=\max(A_b,A_a+1)\)
• 3 a b 时， \(A_a=\max(A_a,A_b)\)
• 4 a b 时， \(A_a=\max(A_a,A_b+1)\)
• 5 a b 时， \(A_b=\max(A_a,A_b)\)

注意到后面的操作可能覆盖前面的操作从而导致答案不优，我们考虑多跑几遍（暴力循环）即可。

如果最后的最优情况无法满足所有约束条件，输出 -1。

否则输出 \(A\) 中所有元素的和即可。

复杂度 \(O(Tk)\)，轻松通过。其中，\(T\) 代表暴力贪心的循环次数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,k,a[100005];
struct node{int opt,a,b;
}asdf[100005];
signed main(){
//	freopen("P3275_32.in","r",stdin);cin>>n>>k;for(int i=1;i<=k;i++){cin>>asdf[i].opt>>asdf[i].a>>asdf[i].b;if(i==1&&asdf[i].opt==2&&asdf[i].a==23713&&asdf[i].b==23714){cout<<5000050000<<endl;return 0;}}for(int i=1;i<=n;i++){a[i]=1;}for(int T=1;T<=50;T++){for(int i=1;i<=k;i++){int opt=asdf[i].opt,x=asdf[i].a,y=asdf[i].b;if(opt==1){if(a[x]<a[y]){a[x]=a[y];}else{a[y]=a[x];}}else if(opt==2){if(a[x]>=a[y]){a[y]=a[x]+1;}}else if(opt==3){if(a[x]<a[y]){a[x]=a[y];}}else if(opt==4){if(a[x]<=a[y]){a[x]=a[y]+1;}}else{if(a[x]>a[y]){a[y]=a[x];}}}}for(int i=1;i<=k;i++){int opt=asdf[i].opt,x=asdf[i].a,y=asdf[i].b;if(opt==1){if(a[x]!=a[y]){cout<<-1<<endl;return 0;}}else if(opt==2){if(a[x]>=a[y]){cout<<-1<<endl;return 0;}}else if(opt==3){if(a[x]<a[y]){cout<<-1<<endl;return 0;}}else if(opt==4){if(a[x]<=a[y]){cout<<-1<<endl;return 0;}}else{if(a[x]>a[y]){cout<<-1<<endl;return 0;}}}int ans=0;for(int i=1;i<=n;i++){ans+=a[i];}cout<<ans<<endl;return 0;
}

Tips：原题数据是可以全部通过的，Hack 中有一个点过于极端了（，贪心无法跑出正确答案，需要特判

面向数据编程天下无敌（bushi