• 题目大意
  给定一个长度为n的序列，将他分成两个集合，要求：1. 集合元素个数相差最少 2. 集合元素和相差最大。输出：元素个数差和元素和之差。
• 思路
  分奇偶性讨论一下。
• Code

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int n,a[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int s1=0,s2=0;
	for(int i=1;i<=n/2;i++) s1+=a[i];
	for(int i=n/2+1;i<=n;i++) s2+=a[i];
	if(n%2==0)
	{
		cout<<0<<' '<<s2-s1;
	}
	else
	{
		cout<<1<<' '<<s2-s1;
	}
	
	return 0;
}

1114 Family Property (25 分)

• 题目大意
  给定一些家庭关系，让你输出有几个家庭，每个家庭的信息：1.家庭中最小编号id 2. 家庭中人数M 3. 家庭中财产平均数avg_aets 4.家庭中占用面积的平均数avg_area
  并要求：按平均占用面积由大到小，id由小到大的顺序输出。
• 思路
  经典并查集，但是要有一个好的逻辑方便对输入输出进行处理
  第一个代码写了一会儿只有22分，但是不想调了；第二个代码是正解满分。
• Code

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;

int n,fa[N],st[N],id[N],M[N];
int a,b,c,k,d;
double sets[N],area[N],sum_sets[N],sum_area[N];
set<int> v;
struct node{
	int first;
	int second;
	int key;
}ans[N];
bool cmp(const struct node x,const struct node y)
{
	if(x.first>y.first) return true;
	else if(x.first==y.first&&x.second<y.second) return true;
	return false;
}
void init()
{
	for(int i=0;i<=9999;i++) fa[i]=i;
}

int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}

void un(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) fa[fx]=fy;
	return;	
}

int main()
{
	cin>>n;
	init();
	for(int i=0;i<=9999;i++) id[i]=999999;
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b>>c;
		v.insert(a);
		if(b!=-1) 
		{
			un(a,b);	
			v.insert(b);
		}
		if(c!=-1)
		{
			un(a,c);	
			v.insert(c);
		} 
		cin>>k;
		while(k--)
		{
			cin>>d;
			un(a,d);
			v.insert(d);
		}
		cin>>sets[a]>>area[a];	
	}
	for(auto i:v) find(i);
	for(auto i:v) 
	{
		st[fa[i]]=1;
		id[fa[i]]=min(id[fa[i]], i);
		M[fa[i]]++;
		sum_sets[fa[i]]+=sets[i];
		sum_area[fa[i]]+=area[i];
	}
	int cnt=0;
	for(auto i:v)
	{
		if(st[i]) cnt++;
	}
	cout<<cnt<<endl;
	int idx=0;
	for(auto i:v)
		if(st[i])
		{
			ans[++idx].first=sum_area[i]/M[i];
			ans[idx].second=id[i];
			ans[idx].key=i;
		}
	sort(ans+1,ans+idx+1,cmp);
	for(int i=1;i<=idx;i++)
	{
		printf("%04d %d %.3lf %.3lf\n",ans[i].second, M[ans[i].key], sum_sets[ans[i].key]/M[ans[i].key], sum_area[ans[i].key]/M[ans[i].key]);
	}
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;

int n;
int p[N], c[N], hc[N], ha[N];
bool st[N];

struct Edge
{
    int a, b;
}e[N];

struct Family
{
    int id, c, hc, ha;

    bool operator< (const Family &t) const
    {
        // ha / c ? t.ha / t.c
        if (ha * t.c != t.ha * c) return ha * t.c > t.ha * c;
        return id < t.id;
    }
};

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n;

    int m = 0;
    for (int i = 0; i < n; i ++ )
    {
        int id, father, mother, k;
        cin >> id >> father >> mother >> k;

        st[id] = true;
        if (father != -1) e[m ++ ] = {id, father};
        if (mother != -1) e[m ++ ] = {id, mother};
        for (int j = 0; j < k; j ++ )
        {
            int son;
            cin >> son;
            e[m ++ ] = {id, son};
        }

        cin >> hc[id] >> ha[id];
    }

    for (int i = 0; i < N; i ++ ) p[i] = i, c[i] = 1;
    for (int i = 0; i < m; i ++ )
    {
        int a = e[i].a, b = e[i].b;

        st[a] = st[b] = true;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            if (pb > pa) swap(pa, pb);
            c[pb] += c[pa];
            hc[pb] += hc[pa];
            ha[pb] += ha[pa];
            p[pa] = pb;
        }
    }

    vector<Family> family;
    for (int i = 0; i < N; i ++ )
        if (st[i] && p[i] == i)
            family.push_back({i, c[i], hc[i], ha[i]});

    sort(family.begin(), family.end());

    cout << family.size() << endl;
    for (auto f : family)
        printf("%04d %d %.3lf %.3lf\n", f.id, f.c, (double)f.hc / f.c, (double)f.ha / f.c);

    return 0;
}