论坛 › 数据结构与算法 › 问一下各位佬，为什么这段代码只能过10%的数据？

猪头少年.zm 发表于 2024-4-20 14:53:30

问一下各位佬，为什么这段代码只能过10%的数据？

题目描述：
小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 ai。在闲暇之余，小明决定在班级里组织一场拔河比赛。

为了保证比赛的双方实力尽可能相近，需要在这 n 名同学中挑选出两个队伍，队伍内的同学编号连续:{al1, al1+1, ..., ar1−1, ar1} 和 {al2, al2+1, ..., ar2−1, ar2}，其中 l1 ≤ r1 < l2 ≤ r2。

两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。


【评测用例规模与约定】

对于 20% 的评测用例，保证 n ≤ 50。

对于 100% 的评测用例，保证 n ≤ 1e3，ai ≤ 1e9。



说一下我的思路：
把数组从小到大排列好。对于这个已经排列好的数组而言，有一个头指针top，一个尾指针rear，还有一个mid指针 =(top + rear) / 2 。

将从top加到mid的值即为lef，mid加到rear的值记录为rig

如果lef<rig,则记录temp = rig-lef

如果lef>=rig，则判断temp，lef-rig谁更小，输出小的那一个

但是不知道为什么只能过10%的数据，希望各位大佬能够帮小萌新解惑

以下是源代码//////////
//////////#include<bits/stdc++.h>
//////////using namespace std;
//////////
//////////static int N = 1e5;
//////////int str;
//////////int end1;
//////////int length;
//////////bool isPrime(int n)        //为true时为素数
//////////{
//////////        if (n < 2)
//////////                return false;
//////////        for (int i = 2;i * i <= n;i++)
//////////        {
//////////                if (n % i == 0)
//////////                        return false;
//////////        }
//////////        return true;
//////////}
//////////
//////////int Prime()
//////////{
//////////        vector<bool>flag(N);
//////////        vector<int>st;
//////////        cin >> str >> end1;
//////////        for (int i = str;i <= end1;i++)
//////////        {
//////////                st.push_back(i);
//////////        }
//////////        length = st.size();
//////////        for (int i = 0;i < length;i++)
//////////        {
//////////                if (isPrime(st))//isPrime为真的时候是素数
//////////                {
//////////                        flag = true;
//////////                        for (int j = 1;j * st <= st;j++)
//////////                        {
//////////                                flag] = false;
//////////                        }
//////////                }
//////////        }
//////////        for (int i = 0;i < length;i++)
//////////        {
//////////                if (flag)
//////////                        cout << st << " ";
//////////        }
//////////        puts("");
//////////        return 0;
//////////}
//////////
//////////
//////////int main()
//////////{
//////////        ios::sync_with_stdio(0);
//////////        cin.tie(0);
//////////        cout.tie(0);
//////////        int i =1;
//////////        cin >> i;
//////////        while (i--)
//////////                Prime();
//////////        return 0;
//////////}
//////////
////////#include <iostream>
////////#include <vector>
////////#include <cmath>
////////using namespace std;
////////
////////void sieveOfEratosthenes(int start, int end1) {
////////    vector<bool> isPrime(end1 - start + 1, true);
////////    for (int i = 2; i * i <= end1; ++i) {
////////      for (int j = max(2, (start + i - 1) / i) * i; j <= end1; j += i) {
////////            isPrime = false;
////////      }
////////    }
////////    for (int i = max(2, start); i <= end1; ++i) {
////////      if (isPrime) {
////////            cout << i << " ";
////////      }
////////    }
////////    cout << endl;
////////}
////////
////////int main() {
////////    int t;
////////    cin >> t;
////////    while (t--) {
////////      int start, end1;
////////      cin >> start >> end1;
////////      sieveOfEratosthenes(start, end1);
////////    }
////////    return 0;
////////}
//////全排列
//////
//////#include<bits/stdc++.h>
//////using namespace std;
//////typedef long long ll;
//////int st;
//////bool ise;
//////int num = 3;
//////
//////void dfs(int step)        //好像又犯了相同的错误
//////{
//////        //一定要明确每个参数的意义
//////        //边界条件
//////        if (step == num+1)
//////        {
//////                for (int i = 1; i < step;i++)
//////                {
//////                        cout << st;
//////                }
//////                cout << endl;
//////                return ;
//////        }
//////        //循环条件
//////        for (int i = 1;i < num + 1;i++)//切记i表示的是手中的牌
//////        {
//////                if (!ise)
//////                {
//////                        st = i;
//////                        ise = true;
//////                        dfs(step + 1);
//////                        ise = false;
//////                }
//////        }
//////}
//////void solve()
//////{
//////        dfs(1);
//////}
//////
//////int main()
//////{
//////        ios::sync_with_stdio(0);
//////        cout.tie(0);
//////        cin.tie(0);
//////        int i = 1;
//////        while (i--)
//////                solve();
//////        return 0;
//////}
////
////#include<bits/stdc++.h>
////using namespace std;
////#define int long long
////#define endl '\n'
////#define pp ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
////const int N = 1e5 + 1;
////vector<int>a;
////int s;
////int n;
////void solve() {
////    pp;
////    cin >> n;
////    for (int i = 0;i < n;i++)cin >> s;
////    sort(s, s + n);//s表示h
////    for (int i = 0;i < n;i++)
////    {
////      for (int j = 1;j <= sqrt(s);j++)
////      {
////            if (s % j == 0)
////            {
////                a.push_back(s);
////                //需要在满足是因子的基础上判断是否是乘方因子，放在外面是错的
////                if (s / j != j)
////                  a / j].push_back(s);
////            }
////      }
////    }
////
////    for (int i = N - 1;i >= 0;i--)
////    {
////      if (a.size() >= 3)
////      {
////            cout << a;
////            for (int j = 1;j < 3;j++)cout << " " << a;
////            break;
////      }
////    }
////    return;
////}
////
////signed main() {
////    int T = 1;
////    while (T--)solve();
////    return 0;
////}
////
//
//
////不会写就暴力
//#include <iostream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//typedef long long ll;
//ll temp;
//int cmp(ll x,ll y)
//{
//        return x > y;
//}
//void solve()
//{
//        ll n, p, q;
//        cin >> n>>p>>q;
//        vector<ll>a(n);
//        {
//                for (ll i = 0;i < n;i++)
//                {
//                        cin >> a;
//                }
//        }
//        ll ans = 0;
//        sort(a.begin(), a.end());
//        for (temp = n - 1;temp > n - q - 1;temp--)
//        {
//                a = sqrt(a);
//        }
//        sort(a.begin(), a.end(),cmp);
//        for (ll i = 0;i < q;i++)
//        {
//                a = a / 2;
//        }
//        for (ll i = 0;i < n;i++)
//        {
//                ans += a;
//        }
//        cout <<ans;
//}
//int main()
//{
//        ios::sync_with_stdio(0);
//        cin.tie(0);
//        cout.tie(0);
//        int i = 1;
//        while (i--)
//        {
//                solve();
//        }
//}

//拔河，简单解法
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define def(x) cout<<x
#define endl '\n'
#define M 0x3f3f3f3f3f3f3f3f
//const int N = 10e3 + 10;
ll num;
//int a;                //这边有点问题，数组太大了怎么办？
void solve()
{
       
        cin >> num;
        vector<ll>a;
        ll temp;
        for (ll i = 0;i < num;i++)
        {
                cin >> temp;
                a.push_back(temp);
        }
        sort(a.begin(), a.end());
        ll top = 0, rear = num - 1;
        ll mid = (top+rear)/2;
        ll lef, rig;
        ll temp1 = 0;
        while (1)
        {
                //每次更新的时候进行重置
                lef = 0;
                rig = 0;
                for (ll i = 0; i < mid; i++)
                {
                        lef += a;
                }
                for (ll i = mid;i <= rear;i++)
                {
                        rig = rig + a;
                }
                //只要少给一个，右边一定大
                if (lef >= rig )
                {
                        if (temp1 < lef - rig)
                        {
                                def(temp1);
                        }
                        else
                        {
                                def(lef - rig);
                        }
                        return;
                }
                temp1 = rig - lef;
                mid++;       
        }

}
int main()
{
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int t = 1;
        while (t--)
        {
                solve();
        }
        return 0;
}

FishC 发表于 2024-4-20 14:53:51

看起来你的代码逻辑出现了一些问题。首先，你的思路是正确的，需要将数组按升序排列，并找出两个队伍的分界点mid。但是在找到mid之后，你的代码逻辑出现了问题。

首先，temp1应该在while循环外面进行定义，否则每次循环都会重置为0，导致计算错误。

其次，你计算lef和rig的方式有误。对于lef，应该累加从top到mid的所有元素，而不是只累加a。同样地，rig也应该累加从mid+1到rear的所有元素。

最后，你的条件判断有误，应该判断temp1和abs(lef-rig)的大小关系，而不是temp1和lef-rig的大小关系。

下面是修改后的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a;
    }
    sort(a.begin(), a.end());// 对数组进行排序

    int top = 0, rear = n - 1;
    int mid = (top + rear) / 2;
    int lef, rig;
    int temp1 = 0;
    while (1) {
      lef = 0;
      rig = 0;
      for (int i = top; i <= mid; i++) {
            lef += a;
      }
      for (int i = mid + 1; i <= rear; i++) {
            rig += a;
      }
      if (temp1 < abs(lef - rig)) {
            temp1 = abs(lef - rig);
      } else {
            break;
      }
      mid++;
    }
    cout << temp1 << endl;
}

int main() {
    solve();
    return 0;
}

现在你可以试着运行这段代码，并测试一下是否能够正确解决问题。如果还有其他问题，请随时向我提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

查看完整版本: 问一下各位佬，为什么这段代码只能过10%的数据？