fork(1) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. /**
  6.  * Created by arpit on 4/2/17.
  7.  */
  8. class StudentArrangement {
  9.  
  10.     static final int MAX =100000;
  11.     static int [] a =new int[MAX];
  12.     static int[] count =new int[MAX];
  13.     static int[]next=new int[MAX];
  14.  
  15.     public static void main(String[] args) throws IOException {
  16.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  17.         int n,m,k;
  18.         String[]s;
  19.  
  20.         s=br.readLine().split("\\s");
  21.         n=Integer.parseInt(s[0]);
  22.         m=Integer.parseInt(s[1]);
  23.         k=Integer.parseInt(s[2]);
  24.  
  25.         s=br.readLine().split("\\s");
  26.         for (int i = 0; i < n; i++) {
  27.             a[i]=Integer.parseInt(s[i])-1;
  28.         }
  29.         System.out.println(solve1(a, n, m, k));
  30.     }
  31.  
  32.     private static int solve1(int[] preference, int n, int m, int k) {
  33.         int cnt=0;
  34.         if (n>(m*k)){
  35.             cnt=n-m*k;
  36.             n=m*k;
  37.         }
  38.         initNext(m);
  39.  
  40.         for (int i = 0; i < n; i++) {
  41.             if (count[preference[i]]<k)
  42.                 count[preference[i]]++;
  43.             else if (count[next[preference[i]]]<k){
  44.                 count[next[preference[i]]]++;
  45.                 cnt++;
  46.             }
  47.             else {
  48.                 nextVacantRow(preference[i],k);
  49.                 count[next[preference[i]]]++;
  50.                 cnt++;
  51.             }
  52.         }
  53.         return cnt;
  54.     }
  55.  
  56.     private static int nextVacantRow(int i,int k) {
  57.         int temp=next[i];
  58.         if (count[temp]<k){
  59.             next[i]=temp;
  60.             return temp;
  61.         }
  62.         next[i]=nextVacantRow(next[i],k);
  63.         return next[i];
  64.     }
  65.  
  66.     private static void initNext(int m) {
  67.         next[m-1]=0;
  68.         for (int i = 0; i < m - 1; i++) {
  69.             next[i]=i+1;
  70.         }
  71.     }
  72.  
  73.     private static int solve(int[] preference, int n, int m, int k) {
  74.         int cnt=0;
  75.         if (n>(m*k)){
  76.             cnt=n-m*k;
  77.             n=m*k;
  78.         }
  79.  
  80.         for (int p = 0; p < n; p++) {
  81.  
  82.             if (count[preference[p]]<k){
  83.                 count[preference[p]]++;
  84.             }
  85.             else {
  86.                 int temp= nextEmptySit(preference[p] + 1, m, k);
  87.                 if (temp>=0)
  88.                     count[temp]++;
  89.                 cnt++;
  90.             }
  91.             //System.out.println(ans);
  92.         }
  93.         return cnt;
  94.     }
  95.  
  96.     private static int nextEmptySit(int row, int m, int k) {
  97.         while (true){
  98.             if (count[row%m]<k){
  99.                 return row%m;
  100.             }
  101.             row++;
  102.         }
  103.     }
  104. }
  105.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
5 2 2
1 1 2 2 2
stdout
copy 
1
https://ideone.com/aolRdX
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!