总共有n只鸡参与斗鸡联赛,第i只鸡到目前为止已经积了a i个积分。

接下来还有m场比赛要进行,第i场比赛的对阵双方是编号为u iv i的鸡。积分规则是:胜方加三分,败方不得分,若战平则双方各得一分。

请你计算在最好的情况下,我们的一号选手(炸鸡)能够排到第几名。

注意若有多鸡并列,则排名取并列的排名,且不影响随后的排名(例如两只鸡并列第二名,则都视为第二名,排名其后的下一只鸡视为第四名)。

输入格式

输入第一行包括一个整数$(1 \leq T \leq 100)$,样例组数。

对于每组样例:

  • 第一行输入两个整数n,m $(2 \leq n \leq 10,1 \leq m \leq 10)$,含义如题面所述。
  • 第二行输入n个整数a i $(0 \leq a i \leq 100)$,表示第i只鸡当前已经有的积分。
  • 接下来的m行,每行有两个正整数u i,v i,$(1 \leq u i,v i \leq n, u i \neq v i)$,表示第i场比赛的对阵双方。

输出格式

对每组样例,输出一个整数表示一号选手在最好的情况下能够排到第几名。

输入样例:

3
4 3
2 4 5 8
1 2
1 4
2 4
3 1
3 1 1
2 3
6 6
1 2 3 4 5 6
2 3
2 3
3 4
4 5
5 6
6 1

输出样例:

1
1
4

题目分析

题目说是贪心,其实是骗人的(恼 。

考虑贪心:

  • 我们需要在读入数据的时候,保证与 1 有关的比赛都是 1 胜。

这样的话,在读入数据结束后,我们可以得到 1 的最高得分。 然后我们再考虑与 1 无关的比赛, 将会出现两种情况。

  • 如果比赛的某一方或两者的得分已经比 1 高,那么让这只鸡(如果两者得分都比 1 高,那么任意一只鸡)获胜。(因为它已经超过了 1, 我们只需要将损失降低到最小,即让另外一只鸡的得分不增加)
  • 如果比赛双方的得分均比 1 小。 (我在这个情况的贪心分析中卡住了)

我们可以看到数据范围: $$ 2 \leq n \leq 10,1 \leq m \leq 10 $$ 很明显,我们可以 DFS 出答案。

其中每层递归中有 3 种情况,递归树是一个高度最高为 10 的三叉树。

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
const int N = 110;

int t;
int dfs(vector <PII> sc, vector <PII> ct, int i) {
    if(i >= (int)ct.size()) {
        sort(sc.begin() + 1, sc.end(), [](const PII& a, const PII& b) {
            if(a.y == b.y) return a.x < b.x;
            return a.y > b.y;
        });
        for(int i = 1; i < (int)sc.size(); ++i) if(sc[i].x == 1) return i;
        return sc.size() - 1;
    }
    int p1 = ct[i].x, p2 = ct[i].y, ans = sc.size() - 1;
    if(p1 == 1 || p2 == 1) {
        sc[1].y += 3;
        return dfs(sc, ct, i + 1);
    }
    sc[p1].y += 3;
    int a1 = dfs(sc, ct, i + 1);
    sc[p1].y -= 3, sc[p2].y += 3;
    int a2 = dfs(sc, ct, i + 1);
    sc[p2].y -= 3;
    ans = min(a1, a2);
    sc[p1].y += 1, sc[p2].y += 1;
    int b = dfs(sc, ct, i + 1);
    sc[p1].y -= 1, sc[p2].y -= 1;
    return min(ans, b);
}
int solve() {
    int n, m;
    cin >> n >> m;
    vector <PII> sc(n + 1), ct(m);
    for(int i = 1; i <= n; ++i) cin >> sc[i].y, sc[i].x = i;
    for(int i = 0; i < m; ++i) cin >> ct[i].x >> ct[i].y;
    return dfs(sc, ct, 0);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}
分类: DFS

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status