杀人游戏(hdu2211)插入法
2024-10-21 18:52:14
杀人游戏
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1375 Accepted Submission(s): 267
Problem Description
不知道你是否玩过杀人游戏,这里的杀人游戏可没有法官,警察之类的人,只有土匪,现在已知有N个土匪站在一排,每个土匪都有一个编号,从1到N,每次杀人时给定一个K值,从还活着的土匪中,编号从小到大的找到K个人,然后杀掉,继续往下,直到找遍,然后继续从剩下的土匪中,编号从小到大找到第K个活着的土匪,然后杀掉。比如,现在有10个土匪,K为3,第一次杀掉3,6,9号的土匪,第二次杀掉4,8号土匪,第三次杀掉5号土匪,第四次杀掉7号土匪,第五次杀掉10号土匪,我们看到10号土匪是最后一个被杀掉的(从1到K-1的土匪运气好,不会被杀!)。现在给定你一个N和一个K,问你最后一个被杀掉的土匪的编号是多少。
Input
第一行有一个T(T<=10000),接下来有T组数据,每组中包含一个N(N<2^31)和一个K(3<=K<=100&&K<N)。
Output
对于每组数据,输出最后被杀的土匪的编号。
Sample Input
1
10 3
Sample Output
10
拖了好久啊,,,,,,今天要谢谢老板哈!插数,,,原来如此!
这是一道很有趣的题目,
#include<stdio.h>
int main()
{
__int64 t,n,k,count,luck,s,p,i;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&k);
p=k-;//插入周期eg:k=3,那么p=2;两个一插
for(s=k;s<n;)//s为标记,来标记luckboy的位置
{
i=(s-)/p;//计算s前面插几个
luck=s;//luck是记录上一个s的值
s=s+i;
}
printf("%I64d\n",luck);
}
return ;
}
以题例为例,他的流程图如下,s代表luck boy的位置,数字带下划线表示刚插入的数
是不是 so easy 啊! 关键是方法!!!
1 2 s(3)
1 2 3 s(4)
1 2 3 s(5) 6
1 2 3 6 s(7) 9
1 2 3 6 9 s(10) 12
够短小吧,再者我之前的代码是:
#include<stdio.h>
int main()
{
int t,k;
__int64 i,j,n,count,p;
__int64 a[],luck; scanf("%d",&t);
while(t--)
{
scanf("%I64d%d",&n,&k);
for(i=;i<=n;i++)
a[i]=i;
count=;
for(i=k;i<=n;i++)
{
if(a[i]%k==)
{a[i]=;count++;} }
for(i=,j=;(n-count)>=k;i++)
{ if(a[i]!=)
j++;
if(j==k)
{luck=a[i];a[i]=;count++;j=;}
if(i==n)
{i=;j=;}
}
printf("%I64d\n",luck); }
return ; }
这就是差距,大神就是大神,学长牛牛,,,我也要加油
最新文章
- Java关键字final、static使用总结
- 从exchange2010上面删除特定主题或特定时间的邮件
- springmvc+ajaxFileUpload上传文件(前后台彻底分离的情况下)
- Linux C 程序 进程控制(17)
- MapReduce编程系列 — 5:单表关联
- 第九篇、Swift的基本使用
- Java基础知识强化100:JVM 内存模型
- [Kubernetes]谈谈容器跨主机网络
- Visual Studio 2017中使用正则修改部分内容
- 我的tensorflow学习1
- video 在移动端播放禁止全屏
- 企业落地Kubernetes的问题与对策
- 使用sso(cas)的时候报单点登录service不匹配问题分析及解决
- 很受欢迎的vue前端UI框架
- centos7安装go语言环境
- 【Codeforces711E】ZS and The Birthday Paradox [数论]
- 在linux中使用shell来分析统计日志中的信息
- lockingModel in log4net 日志文件不能被其他进程写入
- Zeroc Ice 发布订阅者之demo Icestorm之clock
- MySQL使用总结