題目描述

lxhgww最近迷上了一款游戲，在游戲里，他擁有很多的裝備，每種裝備都有2個(gè)屬性，這些屬性的值用[1,10000]之間的數(shù)表示。當(dāng)他使用某種裝備時(shí)，他只能使用該裝備的某一個(gè)屬性。并且每種裝備最多只能使用一次。游戲進(jìn)行到最后，lxhgww遇到了終極boss，這個(gè)終極boss很奇怪，攻擊他的裝備所使用的屬性值必須從1開始連續(xù)遞增地攻擊，才能對(duì)boss產(chǎn)生傷害。也就是說一開始的時(shí)候，lxhgww只能使用某個(gè)屬性值為1的裝備攻擊boss，然后只能使用某個(gè)屬性值為2的裝備攻擊boss，然后只能使用某個(gè)屬性值為3的裝備攻擊boss……以此類推。現(xiàn)在lxhgww想知道他最多能連續(xù)攻擊boss多少次？

輸入輸出格式

輸入格式：

?

輸入的第一行是一個(gè)整數(shù)N，表示lxhgww擁有N種裝備接下來N行，是對(duì)這N種裝備的描述，每行2個(gè)數(shù)字，表示第i種裝備的2個(gè)屬性值

?

輸出格式：

?

輸出一行，包括1個(gè)數(shù)字，表示lxhgww最多能連續(xù)攻擊的次數(shù)。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 3 1 2 3 2 4 5 輸出樣例#1：?復(fù)制 2

說明

Limitation

對(duì)于30%的數(shù)據(jù)，保證N < =1000

對(duì)于100%的數(shù)據(jù)，保證N < =1000000

Solution：

以屬性值為左頂點(diǎn)，編號(hào)1~n為右頂點(diǎn)連邊，二分匹配即可，注意因?yàn)橐B續(xù)，所以第一個(gè)無法匹配的就要break。

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include<bits/stdc++.h> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; typedef long long ll; template <class T> inline void rd(T &ret){char c;ret = 0;while ((c = getchar()) < '0' || c > '9');while (c >= '0' && c <= '9'){ret = ret * 10 + (c - '0'), c = getchar();} } struct node{int v,nx;}p[2000005]; int n,maxn,ans,tot,vis[10005],mh[1000006],head[10006]; void addedge(int u,int v){p[++tot].v=v,p[tot].nx=head[u],head[u]=tot;} int match(int cur){if(vis[cur])return 0;vis[cur]=1;for(int i=head[cur];i;i=p[i].nx){if(!mh[p[i].v]||match(mh[p[i].v])){mh[p[i].v]=cur;return 1;}}return 0; } int main(){rd(n);REP(i,1,n){int u,v;rd(u),rd(v);addedge(u,i),addedge(v,i);maxn=max(maxn,max(u,v));}REP(i,1,maxn){memset(vis,0,sizeof(vis));if(match(i))ans++;else break;}cout<<ans<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/czy-power/p/10396893.html

總結(jié)

以上是生活随笔為你收集整理的连续攻击游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。