首页 > 专题系列 > Java解POJ > POJ 3665 iCow [解题报告] Java
2013
11-13

POJ 3665 iCow [解题报告] Java

iCow

问题描述 :

Fatigued by the endless toils of farming, Farmer John has decided to try his hand in the MP3 player market with the new iCow. It is an MP3 player that stores N songs (1 ≤ N ≤ 1,000) indexed 1 through N that plays songs in a "shuffled" order, as determined by Farmer John’s own algorithm:

  • Each song i has an initial rating Ri (1 ≤ Ri ≤ 10,000).
  • The next song to be played is always the one with the highest rating (or, if two or more are tied, the highest rated song with the lowest index is chosen).
  • After being played, a song’s rating is set to zero, and its rating points are distributed evenly among the other N-1 songs.
  • If the rating points cannot be distributed evenly (i.e., they are not divisible by N-1), then the extra points are parceled out one at a time to the first songs on the list (i.e., R1 , R2 , etc. — but not the played song) until no more extra points remain.

This process is repeated with the new ratings after the next song is played.

Determine the first T songs (1 ≤ T ≤ 1000) that are played by the iCow.

输入:

* Line 1: Two space-separated integers: N and T
* Lines 2..N+1: Line i+1 contains a single integer: Ri

输出:

* Lines 1..T: Line i contains a single integer that is the i-th song that the iCow plays.

样例输入:

3 4
10
8
11

样例输出:

3
1
2
3

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 int arr[]=new int[10010];
 int n,m,i,j,u;
 n=sc.nextInt();
 m=sc.nextInt();
 for(i=0;i< n;i++)
    arr[i]=sc.nextInt();
 for(i=0;i< m;i++)
 {
   int maxx=-1,tag=0;
   for(j=0;j< n;j++)
    if(arr[j]>maxx)
    {
	maxx=arr[j];
	tag=j;
     }
   System.out.printf("%d\n",tag+1);
   int add=arr[tag]/(n-1);
   int mod=arr[tag]%(n-1);
   for(j=0;j< n;j++)
	arr[j]+=add;
   for(j=0;j< mod;j++)
   {
	arr[j]++;
	if(j==tag) mod++;
   }
   arr[tag]=0;
  }
 }
}

  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。