煩惱的高考志愿

題目背景

計算機競賽小組的神牛 V 神終于結(jié)束了高考，然而作為班長的他還不能閑下來，班主任老 t 給了他一個艱巨的任務：幫同學找出最合理的大學填報方案?？墒?v 神太忙了，身后還有一群小姑娘等著和他約會，于是他想到了同為計算機競賽小組的你，請你幫他完成這個艱巨的任務。

題目描述

現(xiàn)有 $m$ 所學校，每所學校預計分數(shù)線是 $a_i$。有 $n$ 位學生，估分分別為 $b_i$。

根據(jù) $n$ 位學生的估分情況，分別給每位學生推薦一所學校，要求學校的預計分數(shù)線和學生的估分相差最小（可高可低，畢竟是估分嘛），這個最小值為不滿意度。求所有學生不滿意度和的最小值。

輸入格式

第一行讀入兩個整數(shù) $m,n$。$m$ 表示學校數(shù)，$n$ 表示學生數(shù)。

第二行共有 $m$ 個數(shù)，表示 $m$ 個學校的預計錄取分數(shù)。第三行有 $n$ 個數(shù)，表示 $n$ 個學生的估分成績。

輸出格式

輸出一行，為最小的不滿度之和。

樣例 #1

樣例輸入 #1

4 3
513 598 567 689
500 600 550

樣例輸出 #1

32

提示

數(shù)據(jù)范圍：

對于 $30\%$ 的數(shù)據(jù)，$1\le n,m\le 1000$，估分和錄取線 $\le 10000$；

對于 $100\%$ 的數(shù)據(jù)，$1\le n,m\le 100000$，估分和錄取線 $\le 1000000$ 且均為正整數(shù)。文章來源地址http://www.zghlxwxcb.cn/news/detail-432925.html

lower_bound函數(shù)

#include<iostream>
#include<algorithm>

using namespace std;
int m,n;
const int MAXN=1e5+5;
int a[MAXN];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	sort(a+1,a+m+1);
	long long sum=0;
	for(int i=1;i<=n;i++)
	{
		int score;
		cin>>score;
		//lower_bound函數(shù)返回的是一個指針，而數(shù)組名a也是一個指針，所以相減能得到兩指針之間的距離也就是score應該插入的位置（從小到大順序）
		int t=lower_bound(a+1,a+m+1,score)-a;
		if(t==m+1)//等于m+1說明比數(shù)組a中所有的數(shù)都要大
			sum+=score-a[m];
		else if(t==1)//等于1說明比數(shù)組a中所有的數(shù)都要小
			sum+=a[1]-score;
		else//否則返回的t就是他應該插入的下標，當前數(shù)組的t位置也是第一個大于等于他的數(shù)
			sum+=min(score-a[t-1],a[t]-score);
	}	
	cout<<sum<<endl;
	return 0;
}

二分

#include<iostream>
#include<algorithm>
using namespace std;
int m,n;
const int MAXN=1e5+5;
int a[MAXN];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	sort(a+1,a+m+1);
	long long sum=0;
	for(int i=1;i<=n;i++)
	{
		int score;
		cin>>score;
		int l=1;
		int r=m;
		int mid;
		int ans;
		while(l<r-1)//二分出兩個值
		{
			mid=(l+r)/2;
			if(score>=a[mid])
				l=mid;
			else
				r=mid;
		}
		if(abs(score-a[l])<abs(a[r]-score))//判斷這兩個哪個離score近
	    	ans=abs(score-a[l]);
		else
			ans=abs(a[r]-score);
		sum+=ans;
	}	
	cout<<sum<<endl;
	return 0;
}

到了這里，關(guān)于煩惱的高考志愿的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！