我要招人

去企业版

首页 > 试题广场 >

战力匹配

[编程题]战力匹配

热度指数：143 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

手游设计了一个新玩法，希望将报名参加玩法的所有玩家分为两组，并使得两组的实力相等，每组的实力即为本组内玩家战力的总和。给定所有玩家的战力值，请你找出是否存在一种划分方案能达到策划目的。

输入描述:

输入一个正整数n（玩家数量），后续跟随n个整数（每个玩家的战力）

输出描述:

存在划分方案输出1，不存在输出0

示例1

输入

4 3 1 6 2

输出

算法知识视频讲解

shyefvow

#include <iostream>

#include <vector>

#include <bits/stdc++.h>

using namespace std;

int main() {

int n;

while (cin >> n) {

vector<int> a(n, 0);

int sum = 0;

for (int i=0; i<n; i++) {

cin>>a[i];

sum+=a[i];

}

if (sum & 1) {

cout<<0<<endl;

continue;

}

sum/=2;

if (a[0]==sum) {

cout<<1<<endl;

continue;

}

// dp[i][j]——前i件能否装满j容量

vector<vector<int>> dp(n, vector<int>(sum+1, 0));

for (int i=0; i<n; i++) dp[i][0] = 1;

dp[0][a[0]] = 1;

bool flag = false;

for (int i=1; i<n; i++) {

for (int j=1; j<=sum; j++) {

if (dp[i-1][j]==1) dp[i][j] = 1;

else if (a[i]<=j && dp[i-1][j-a[i]]==1) dp[i][j] = 1;

}

if (dp[i][sum]==1) {

cout<<1<<endl;

flag = true;

break;

}

if (!flag) cout<<0<<endl;

}

编辑于 2024-05-08 14:37:24 回复(0)

C/C++

Humpy1003

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
        sum += nums[i];
    }
    if(sum % 2 != 0) {cout << 0 << endl; return 0;}
    int target = sum / 2;
    vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
    dp[0][0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= target; j++) {
            dp[i+1][j] = dp[i][j];
            if(j >= nums[i]) dp[i+1][j] = dp[i+1][j] | dp[i][j - nums[i]];
        }
    }
    if(dp[n][target])  {cout << 1 << endl; return 0;}
    else {cout << 0 << endl; return 0;}
     
}
// 64 位输出请用 printf("%lld")

编辑于 2024-04-15 20:15:59 回复(1)