poj-3665 iCow(暴力吧)
http://poj.org/problem?id=3665
题目描述
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.
输入
输出
说明
The iCow contains 3 songs, with ratings 10, 8, and 11, respectively. You must determine the first 4 songs to be played.
The ratings before each song played are:
R1 R2 R3
10 8 11 -> play #3 11/2 = 5, leftover = 1
16 13 0 -> play #1 16/2 = 8
0 21 8 -> play #2 21/2 = 10, leftover = 1
11 0 18 -> play #3 ...
刚开始以为要用优先队列,结果越写越麻烦,最后写乱了,wa了,还不如直接暴力做
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <math.h> #define INF 0x3f3f3f3f
#define MAXN 1005
const int mod = 1e9 + ; using namespace std; int d[MAXN]; int main()
{
int N, K;
cin >> N >> K; for (int i = ; i <= N; i++)
scanf("%d", &d[i]); while (K--) {
int maxx = -;
int flag = ;
for (int i = ; i <= N; i++)
if (d[i] > maxx)
maxx = d[i], flag = i;
printf("%d\n", flag);
int temp = d[flag] / (N - );
if (temp) {
for (int i = ; i <= N; i++) {
if (i != flag)
d[i] += temp;
}
}
temp = d[flag] % (N - );
d[flag] = ;
if (temp) {
for (int i = ; i <= N && temp; i++) {
if (i != flag)
d[i]++, temp--;
}
}
} return ;
}
最新文章
- Smarty模版引擎的原理
- js 阻止事件冒泡
- .NET微信公众号开发-6.0模板消息
- linux下的audit服务
- 在 Transact-SQL 中使用 TRY...CATCH
- 关于自定义Adapter实现ListView的使用
- 2014.12.13 ASP.NET文件上传
- Python中单引号、双引号和三引号的区别
- 由基于qml,c++的串口调试工具浅谈qml与c++混合编程
- PHP学习之-1.3 echo语句
- TR90眼镜_百度百科
- MVC支付宝PC网站接口对接
- OpenCV探索之路(十六):图像矫正技术深入探讨
- 使用Travis CI自动部署Hexo到GitHub
- 双11电商剁手节,最全的H5互动营销案例合集
- jQuery源码逐行分析学习02(第一部分:jQuery的一些变量和函数)
- Linux System Programming --Chapter Eight
- 基于MongoDB.Driver的扩展
- [Swift]LeetCode339. 嵌套链表权重和 $ Nested List Weight Sum
- Java课程寒假之开发记账本软件(网页版)之三