贪心模拟）"/>
选机房（贪心模拟）
选机房
Time Limit: 1000ms Memory Limit: 65535KB 64-bit integer IO format: %lld Java class name: Main Prev Submit Status Statistics Discuss Next BNU程序设计大赛就要开始了，决赛地点暂时定在电子楼，因为电子楼有很多各种大小的机房，目前估计参赛的队伍总数为n，但是学校可能没有那么大的机房容纳所有队伍，可能要将选手分配在几个小机房中进行比赛，xyjian老大安排你去选机房，为了让比赛选手相对集中，要求选中机房的总数最少，另外在满足这一前提的情况下尽可能选择较大的机房。现在你得到了BNU所有机房的能容纳队伍数目的情况表，请你编程自动选择机房。Input
输入文件包含多组数据。文件第一行：一个正整数t<=20表示测试数据的组数。
接下来t行表示t组数据，每组数据按照以下格式：
第一行两个正整数n<=100000和k<=1000以空格隔开，表示参赛队的总数和可以选择的机房总数k。
接下来k行每行一个正整数c<=20000。
第1行表示1号机房所能容纳的队伍总数，第2行表示2号机房能容纳的队伍数，以此类推，已知所有k个机房的大小均不相同，并且所有机房的总容量大于n。
Output
对每组数据输出所要选择的机房的编号，每个编号一行，从小到大输出，每组数据后请输出一个空行。Sample Input
2 200 2 300 400 100 5 50 4 20 40 5
Sample Output
21 3 4
题目大意：
这道题说的是，首先给你ｎ个人，然后ｋ个机房，让你给这些人来分配房间，使得所分配的房间能尽可能的大，然后还需要你使用尽可能少的房间数目。
解题思路：
这题一开始写了两个ｃｍｐ，直接ＷＡ了，然后用stable_sort调了下，还是WA，就不装逼了，用了一个b数组专门来记录下标，然后从小到大sort了一次就A了。
代码：
# include<cstdio>
# include<iostream>
# include<algorithm>
# include<cstring>
# include<string>
# include<cmath>
# include<queue>
# include<stack>
# include<set>
# include<map>using namespace std;# define inf 999999999
# define MAX 10000+4struct node
{int id;int val;
}a[MAX];int b[MAX];int cmp ( const struct node & x,const struct node & y )
{return x.val > y.val;
}int cmp2 ( const struct node & x,const struct node & y )
{return x.id < y.id;
}int main(void)
{int t;cin>>t;while ( t-- ){int pos = 0;int n,k;cin>>n>>k;for ( int i = 0;i < k;i++ ){cin>>a[i].val;a[i].id = i+1;}stable_sort(a,a+k,cmp);int sum = 0;int j = 0;int i = 0;while ( sum <= n ){sum += a[i].val;b[j] = a[i].id;i++;j++;}sort(b,b+j);for ( i = 0;i < j;i++ )cout<<b[i]<<endl;if ( t!=0 )cout<<endl;}return 0;
}
更多推荐
选机房（贪心模拟）
发布评论