这题看了一圈，做了好几遍，老做错！！！ - C++教室 - C++论坛

已结贴√ 问题点数：5 回复次数：5

这题看了一圈，做了好几遍，老做错！！！

1899 - 【基础】最满意的方案
题目描述
高考结束了，同学们要开始了紧张的填写志愿的过程，大家希望找一个自己最满意的大学填报方案，请你编程帮忙实现。
现有m(m≤100000)所学校，每所学校预计分数线是ai(ai≤106)。有 n(n≤100000)位学生，估分分别为 bi(bi≤106)。
根据n位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入
第一行读入两个整数m,n。m表示学校数，n表示学生数。第二行共有m个数，表示m个学校的预计录取分数。第三行有n个数，表示n个学生的估分成绩。

输出
一行，为最小的不满意度之和。（数据保证结果<=109）

样例
输入复制
4 3
513 598 567 689
500 600 550
输出复制
32
来源
数组问题二分

标签
数组问题二分

搜索更多相关主题的帖子: 表示　学校　分数　一行　学生　

第 2 楼

得分:5

估计题目拷贝粘贴后，你看都没看一眼。
如果你真是五年级，那应该好好学习，少做无意义的事

程序代码：

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

int main( void )
{
    // ai<=10^6，即最多需要20bits，unsigned足够了
    vector<unsigned> univs;

    // 第一行读入两个整数 m,n。m 表示学校数，n 表示学生数
    size_t m, n;
    cin >> m >> n;

    // 第二行共有 m 个数，表示 m 个学校的预计录取分数
    univs.resize( m );
    copy_n( istream_iterator<unsigned>(cin), m, begin(univs) );
    sort( begin(univs), end(univs) );

    // 第三行有 n 个数，表示 n 个学生的估分成绩
    unsigned delta = 0; // 数据保证结果<=10^9
    for( size_t i=0; i!=n; ++i )
    {
        unsigned score;
        cin >> score;

        auto itor = std::lower_bound( begin(univs), end(univs), score );
        if( itor == end(univs) )
        {
            if( !univs.empty() )
                delta += score-univs.back();
        }
        else
        {
            if( itor == begin(univs) )
                delta += *itor-score;
            else
                delta += min( *itor-score, score-*prev(itor) );
        }
    }
    cout << delta << endl;
}