題目直通車：Codeforces 1027F. Session in BSU

思路：

對第一門考試，使用前一個時間，做標記，表示該時間已經用過，并讓第一個時間指向第二個時間，表示，若之后的考試時間和當前第一個時間沖突時，可以找到當前第二個時間來代替

對每一門考試，如果前一個時間沒有被使用過，直接用前一個時間，否則看前一個時間和后一個時間分別可以指向哪一個時間，假設指向x，y，看x和y的狀態和大小，如果x，y都已經使用過，表示無解，否則的話，選擇較小的，并更新時間指向的狀態

時間的指向狀態更新需要用 map離散數據并用并查集維護

?

#include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<string.h> #include<cstring> #include<algorithm> #include<set> #include<map> #include<fstream> #include<cstdlib> #include<ctime> #include<list> #include<climits> #include<bitset> using namespace std; #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("input.in", "r", stdin);freopen("output.in", "w", stdout); #define left asfdasdasdfasdfsdfasfsdfasfdas1 #define tan asfdasdasdfasdfasfdfasfsdfasfdas typedef long long ll; typedef unsigned int un; const int desll[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; const ll mod=1e9+7; const int maxn=2e6+7; const int maxm=1e6+7; const double eps=1e-4; int m,n; int ar[maxn]; pair<int,int> pa[maxn]; map<int,int> ma; bool wa[maxn]; int f[maxn]; int fin(int x) {return f[x]==x?x:f[x]=fin(f[x]); } int main() {scanf("%d",&n);m=0;for(int i=0;i<n;i++)scanf("%d%d",&pa[i].first,&pa[i].second),ar[m++]=pa[i].first,ar[m++]=pa[i].second;sort(ar,ar+m);m=unique(ar,ar+m)-ar;for(int i=0;i<m;i++){ma[ar[i]]=i;}for(int i=0;i<m;i++)f[i]=i;memset(wa,0,sizeof(wa));int ans=0;for(int i=0;i<n;i++){int a=pa[i].first,b=pa[i].second;if(!wa[ma[a]]){wa[ma[a]]=1;ans=max(ans,a);f[ma[a]]=ma[b];continue;}int x=fin(ma[a]);int y=fin(ma[b]);//分別尋找a，b指向的時間if(wa[x] && wa[y]){printf("-1\n");return 0;}if(wa[x]==false && wa[y]==false){if(ar[x]<ar[y]){f[x]=y;//更新時間指向的狀態wa[x]=1;ans=max(ans, ar[x]);}else{f[y]=x;//更新時間指向的狀態wa[y]=1;ans=max(ans, ar[y]);}}else if(!wa[x]){wa[x]=1;ans=max(ans, ar[x]);}else{wa[y]=1;ans=max(ans, ar[y]);}f[ma[a]]=y;//更新時間指向的狀態}printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/wa007/p/9557601.html

總結

以上是生活随笔為你收集整理的Codeforces 1027F. Session in BSU的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。