「AOJ1081~1090」の編集履歴(バックアップ)一覧に戻る

AOJ1081~1090 - (2012/07/16 (月) 23:23:41) の編集履歴(バックアップ)


1085 Spellcasters

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1085
魔法使いがペアを組んで戦うとき相手に勝てるペアの組み方がいくらあるかを求める問題。

各魔法使いについて自分とペアを組める人の最低値を二分探索で探すだけです。
後はそれより大きな人とは必ずペアが組めるので足しこめば計算終了です。


#include<stdio.h>
#include<algorithm>
#include<vector>
struct wiz{
int no,r;
bool operator<(const wiz& w)const{
	return r<w.r;
}
};
void calc(int n,int s){
std::vector<wiz> vs;
std::vector<wiz>::iterator it;
int r;
wiz w;
for(int i=0;i<n;i++){
	scanf("%d",&r);
	w.r=r;
	vs.push_back(w);
}
std::sort(vs.begin(),vs.end());
for(int i=0;i<n;i++)vs[i].no=i;
int ans=0,m;
for(int i=0;i<n-1;i++){
	w.r=s-vs[i].r;
	it=std::upper_bound(vs.begin(),vs.end(),w);
	if(it==vs.end())continue;
	m=std::max((*it).no,i);
	if(i==m)m++;//自分自身とはペアは組めないのでひいておく
	ans+=n-m;
}

printf("%d\n",ans);
}
int main(){
int n,s;
while(1){
	scanf("%d %d",&n,&s);
	if(n==0&&s==0)break;
	calc(n,s);
}
}