Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Set中不允许相同元素,multiset中允许存在相同的元素

Posted by sunmoonstar at 2006-05-28 20:41:29 on Problem 2833
In Reply To:这题我的两个程序在数据类型使用上完全一样,为什么一个AC,一个WA?请管理员指教。 Posted by:cmc_hope at 2006-05-28 20:07:04
> 以下是AC的程序,朴素的方法:
> 
> /*
> Program		:	The Average
> Author		:	Chen Mingcheng
> */
> 
> #include <iostream>
> #include <iomanip>
> #include <cstdio>
> 
> using namespace std;
> 
> const int maxn = 100;
> 
> int big[maxn], small[maxn];
> int n1, n2, n, l1, l2;
> 
> inline void Swap(int &a, int &b) {
> 	int temp = a;
> 	a = b;
> 	b = temp;
> }
> 
> void Solve() {
> 	__int64 sum = 0;
> 	l1 = l2 = 0;
> 	int i, j, x;
> 	for (i = 0; i < n; i++) {
> 		scanf("%d", &x);
> 		sum += x;
> 		big[l1++] = x;
> 		j = l1 - 1;
> 		for (; j > 0 && big[j] > big[j - 1]; j--)
> 			Swap(big[j], big[j - 1]);
> 		small[l2++] = x;
> 		j = l2 - 1;
> 		for (; j > 0 && small[j] < small[j - 1]; j--)
> 			Swap(small[j], small[j - 1]);
> 		if (l1 > n1) l1--;
> 		if (l2 > n2) l2--;
> 	}
> 	for (i = 0; i < l1; i++)
> 		sum -= big[i];
> 	for (i = 0; i < l2; i++)
> 		sum -= small[i];
> 	long double ans = (long double)sum;
> 	ans /= (long double)(n - n1 - n2);
> 	cout << setiosflags(ios::fixed) << setprecision(6) << ans << endl;
> }
> 
> int main() {
> 	while (1) {
> 		scanf("%d %d %d", &n1, &n2, &n);
> 		if (n1 == 0 && n2 == 0 && n == 0) break;
> 		Solve();
> 	}
> 	return 0;
> }
> 
> 以下是WA的程序,用了<set>
> /*
> Program		:	The Average
> Author		:	Chen Mingcheng
> */
> 
> #include <iostream>
> #include <iomanip>
> #include <cstdio>
> #include <set>
> 
> using namespace std;
> 
> set<int> seq1, seq2;
> int n1, n2, n;
> 
> void Solve() {
> 	seq1.clear();
> 	seq2.clear();
> 	int i, x;
> 	__int64 sum = 0;
> 	long double ans;
> 	for (i = 0; i < n; i++) {
> 		scanf("%d", &x);
> 		sum += x;
> 		seq1.insert(-x);
> 		if (seq1.size() > n1) seq1.erase(--seq1.end());
> 		seq2.insert(x);
> 		if (seq2.size() > n2) seq2.erase(--seq2.end());
> 	}
> 	set<int>::iterator p;
> 	for (p = seq1.begin(); p != seq1.end(); p++)
> 		sum += *p;
> 	for (p = seq2.begin(); p != seq2.end(); p++)
> 		sum -= *p;
> 	ans = (long double)sum;
> 	ans /= (long double)(n - n1 - n2);
> 	cout << setiosflags(ios::fixed) << setprecision(6) << ans << endl;
> }
> 
> int main() {
> 	while (1) {
> 		scanf("%d %d %d", &n1, &n2, &n);
> 		if (n1 == 0 && n2 == 0 && n == 0) break;
> 		Solve();
> 	}
> 	return 0;
> }
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator