1231: ykc买零食
时间限制: 1 Sec 内存限制: 128 MB
题目描述
ykc的班级准备举行班级聚会，而身为生活委员的ykc要为此准备好零食，这天，ykc来到了学校的新起点超市，在转了3个小时候，ykc决定买以下所有的n种零食，其中每种零食的价格可能不一样，而刚好超市有活动，每买m种零食，就可以任选一种不超过k元的零食并免费赠送，而ykc想尽可能的省钱，求ykc的最小花费
输入
输入包含多组数据，以EOF结束，
每组首先输入三个正整数，n,m,k，其中(n,m,k<100)
后输入n个数表示每种零食的价格ai(ai<1000)
输出
输出一个正整数，表示最小花费
样例输入
4 3 2
1 2 3 4
7 3 8
1 2 3 4 5 6 7
样例输出
8
21
import java.util.ArrayList;
import java.util.Scanner; public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<String> w = new ArrayList<String>(); while(sc.hasNext()) {
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt(); int fif = 0;
int num = n/(m+1)==0?0:n/(m+1);
int minmax[] = new int[num];
int a[] = new int[n];
int state[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
fif += a[i];
}
loop:for (int i = 0; i < minmax.length; i++) {
int y = 0;
while(state[y] == 1)
y++;
for (int j = 1; j < a.length; j++) {
if(state[j] == 1)
continue;
if(a[y]>k) {
if(a[j]<=k)
y = j;
}else {
if(a[j]>a[y]&&a[j]<=k)
y = j;
}
}
if(a[y]>k)
a[y] = 0;
state[y] = 1;
minmax[i] = y;
}
for (int j = 0; j < minmax.length; j++) {
fif -= a[minmax[j]];
}
w.add(fif+"");
}
sc.close();
for(String attribute : w) {
System.out.println(attribute);
}
}
}
/**************************************************************
Problem: 1231
User: 20161514325
Language: Java
Result: 正确
Time:245 ms
Memory:13320 kb
****************************************************************/