AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

输入问题总结(笔记)

作者: 作者的头像   Tie ,  2019-09-05 12:00:24 ,  所有人可见 ,  阅读 1038


2


1

用sstream处理输入的问题

  • (01背包DP求解) – 感谢wzc1995

Question

Please solve the following problem in Java.
You are given a list (n <= 100) of positive intergers (value <= 500), 
your program divides these intergers into two groups, such that the difference 
between the sums of these two groups is minimized.

Example 1:
Input: 1 1 1 2 2
Output: 1

Example 2:
Input: 3 9 2 3 5
Output: 0

思路:01背包问题,令j = sum / 2, 模仿yxc学长的思路

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

const int N = 110;

int n;
int v[N];
int f[N]; // 表示前i个数的和小于sum/2,的和的最大值

int main()
{
    //读入数据
    string line;
    int n = 1;
    while (getline(cin, line))
    {
        stringstream ss(line);
        while (ss >> v[n]) n ++ ; // 这里n=6?
    }

    // cout << n << endl;
    // for (int i = 1; i < n; i ++ ) cout << i << " " << v[i] << " " << endl;
    // input: 1 1 1 2 2
    // output: 1 1 1 2 2 为什么n=6? 不应该是5么

    //求 sum/2
    //两组数字和分别越接近sum/2,那么他们的差越小
    int sum = 0;
    for (int i = 1; i < n; i ++ ) 
        sum += v[i];

    for (int i = 1; i < n; i ++ )
        for (int j = sum / 2; v[i] <= j; j -- )
        {
            f[j] = max(f[j], f[j - v[i]] + v[i]);
            //cout << i << " " << j << " " << f[i] << endl;
        }

    //cout << f[n - 1] << endl;
    //cout << sum << endl;

    int ans  = abs((sum - f[sum / 2]) - f[sum / 2]);
    cout << ans << endl;

    return 0;
}

方法一: 用 vector

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int main()
{
    string str;
    while (getline(cin, str))
    {
        vector<int> num;
        int temp;
        istringstream iss(str);
        while (iss >> temp)
        {
            num.push_back(temp);
        }
        // 输出显示
        for (int i = 0; i < num.size(); i++)
            cout << num[i] << " ";
        cout << endl;
    }
}

方法二 : 常规数组

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

const int N = 110, M = 510;

int n, m;
int s[N];
int v[M];
int f[N][N];

int main()
{
    string line;
    int n = 0;
    while (getline(cin, line))
    {
        stringstream ss(line);
        while (ss >> v[n]) n ++ ;
    }
    cout << n << endl;
    for (int i = 0; i < n; i ++ ) cout << v[i] << endl;

    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息