首页 > 专题系列 > Java解POJ > POJ 2454 Jersey Politics [解题报告] Java
2013
11-11

POJ 2454 Jersey Politics [解题报告] Java

Jersey Politics

问题描述 :

In the newest census of Jersey Cows and Holstein Cows, Wisconsin cows have earned three stalls in the Barn of Representatives. The Jersey Cows currently control the state’s redistricting committee. They want to partition the state into three equally sized voting districts such that the Jersey Cows are guaranteed to win elections in at least two of the districts.

Wisconsin has 3*K (1 <= K <= 60) cities of 1,000 cows, numbered 1..3*K, each with a known number (range: 0..1,000) of Jersey Cows. Find a way to partition the state into three districts, each with K cities, such that the Jersey Cows have the majority percentage in at least two of districts.

All supplied input datasets are solvable.

输入:

* Line 1: A single integer, K

* Lines 2..3*K+1: One integer per line, the number of cows in each city that are Jersey Cows. Line i+1 contains city i’s cow census.

输出:

* Lines 1..K: K lines that are the city numbers in district one, one per line

* Lines K+1..2K: K lines that are the city numbers in district two, one per line

* Lines 2K+1..3K: K lines that are the city numbers in district three, one per line

样例输入:

2
510
500
500
670
400
310

样例输出:

1
2
3
6
5
4

温馨提示:

Other solutions might be possible. Note that “2 3″ would NOT be a district won by the Jerseys, as they would be exactly half of the cows.

解题代码:

import java.io.*;  
      
    public class Main{  
      
        //题意   将所有城市分成三部份(每个城市拥有一定的牛) 问至少有两个部份的各自的总牛数大于 500*k    
        // 将所有城市按牛数量排序,从最大的2*k个城市中分成两组(我们已经舍弃最小的k只牛会胜出
        //(当然会不会胜出得看给得数据));  
        // 调整使得剩下 2*k个城市 分成两组都会胜出即大于500*k (注等于500*k不算胜出)  
          
        public static void main(String[] args) throws Exception{  
              
            BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));  
              
            int k = Integer.parseInt(buf.readLine());  
              
            A2 a[] = new A2[3*k];  
              
              
              
            for(int i=0;i< 3*k;i++)  
                a[i] = new A2(Integer.parseInt(buf.readLine()),i);  
              
            java.util.Arrays.sort(a);  
              
            int sa = 0;  
            int sb = 0;  
              
            for(int i=k;i< 2*k;i++){  
                sa += a[i].v;  
                sb += a[i+k].v;  
            }  
              
            while(true){  
                  
                int b1 = (int)(Math.random()*70)%k+k;  
                int b2 = (int)(Math.random()*70)%k+2*k;  
                sa = sa-a[b1].v+a[b2].v;  
                sb = sb-a[b2].v+a[b1].v;  
                int v = a[b1].v;  
                int s = a[b1].s;  
                a[b1].v = a[b2].v;  
                a[b1].s = a[b2].s;  
                a[b2].v = v;  
                a[b2].s = s;  
                if(sa>500*k&&sb>500*k)  
                    break;  
            }  
              
            for(int i=0;i< 3*k;i++)  
                System.out.println(a[i].s+1);  
      
        }  
      
    }  
    class A2 implements Comparable< A2>{  
        int v;  
        int s;  
        public A2(int v, int s) {  
            super();  
            this.v = v;  
            this.s = s;  
        }  
          
        public int compareTo(A2 e) {  
            if(this.v< e.v)  
                return -1;  
            else if(this.v>e.v)  
                return 1;  
            return 0;  
        }  
          
    }

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1