水题。排序枚举。
#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[60],n,m,ans;
int main()
{
int i,j;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<m;i++)
scanf("%d",&a[i]);
sort(a,a+m);
ans=0x3f3f3f3f;
for(i=0;i+n-1<m;i++)
{
if(a[i+n-1]-a[i]<ans)
ans=a[i+n-1]-a[i];
}
printf("%d\n",ans);
}
return 0;
}
1 second
256 megabytes
standard input
standard output
Manao has a monitor. The screen of the monitor has horizontal to vertical length ratio a:b.
Now he is going to watch a movie. The movie's frame has horizontal to vertical length ratio c:d.
Manao adjusts the view in such a way that the movie preserves the original frame ratio, but also occupies as much space on the screen as possible and fits within it completely. Thus, he may have to zoom the movie in or out, but Manao will always change the
frame proportionally in both dimensions.
Calculate the ratio of empty screen (the part of the screen not occupied by the movie) to the total screen size. Print the answer as an irreducible fraction p / q.
A single line contains four space-separated integers a, b, c, d (1 ≤ a, b, c, d ≤ 1000).
Print the answer to the problem as "p/q", where p is a non-negative integer, q is
a positive integer and numbers p and q don't have
a common divisor larger than 1.
1 1 3 2
1/3
4 3 2 2
1/4
Sample 1. Manao's monitor has a square screen. The movie has 3:2 horizontal to vertical length ratio. Obviously, the movie occupies most of the screen if the width of the picture coincides with the width of the screen. In this case, only 2/3 of the monitor
will project the movie in the horizontal dimension:
Sample 2. This time the monitor's width is 4/3 times larger than its height and the movie's frame is square. In this case, the picture must take up the whole monitor in the vertical dimension and only 3/4 in the horizontal dimension:
只可能出现两种情况。即先把图像的长变为和框架的长一样或把图像的高变为和框架的高一样。两种情况比例分别为
(b*c-a*d)/(b*c)和(a*d-b*c)/(a*d)。因为b*c-a*d和a*d-b*c互为相反数所以取正的那个就行了。只是要注意答案要约分。还有分子为0的情况。分母必须为1。所以要特殊处理。
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int a,b,c,d;
int gcd(int x,int y)//最大公约数
{
int t;
while(y)
{
t=x%y;
x=y;
y=t;
}
return x<0?-x:x;//注意正负
}
int main()
{
int p,q,e,f,t,ans,mo;
while(~scanf("%d%d%d%d",&a,&b,&c,&d))
{
p=a*d-b*c;
q=a*d;
e=b*c-a*d;
f=b*c;
if(p==0||e==0)
{
printf("0/1\n");
continue;
}
t=gcd(p,q);
p/=t;
q/=t;
t=gcd(e,f);
e/=t;
f/=t;
if(p>0)
ans=p,mo=q;
else
ans=e,mo=f;
printf("%d/%d\n",ans,mo);
}
return 0;
}
题目意思很简单。就说一人去参加比赛。每答对一题得一分。连续答对k题时先加一分然后总分数乘2然后连续答对题数归0。然后给你题目总数n和他答对题目的个数m问你他能得的最低分是多少。
这题关键是找出最优方案(使得分最低)。
我们设他答错w题。如果w*k>=n。那么他的得分就为n-w。因为这w次错的可以使他答题连续对的小于k个。应该很好理解。
如果w*k<n说明会出现连续答对超过n个的情况。既然这种情况不能避免那么尽量让它出现在前面。因为前面分数少乘以2对总分的影响比较小。所以分数可以分为两部分。
1，前面连续的部分。2，后面被分隔的部分。
后面部分的分数很好求为：(k-1)*w。
而前面的分数也是有规律的。我们假设前面有n*k次答对。
那么分数变化为：2*k,(2*k+k)*2,((2*k+k)*2+k)*2......。抽象出来这就是一个数列递推公式为：
an=2*(an-1+k)。
展开移项后得：an+2*k=2*(an-1+2*k)。设cn=an+2*k。那么cn/cn-1=2。等比数列。
而c0=a0+2*k=2k。那么cn=2*k*2^n。所以an=k*2^(n+1)-2*k。
所以前面的得分为：
k*2^((n-w*k)/k+1)-2*k+(n-w*k)%k。
所以总分最小值就出来了。
ans=k*2^((n-w*k)/k+1)-2*k+(n-w*k)%k+(k-1)*w。
详细见代码：
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll mod=1000000009;
ll pow_mod(ll a,ll i)//快速幂
{
if(i==0)
return 1%mod;
ll temp=pow_mod(a,i>>1);//这里也必须是ll
temp=temp*temp%mod;
if(i&1)
temp=(ll)temp*a%mod;
return temp;
}
ll n,m,w,ans,t,k;
int main()
{
while(~scanf("%I64d%I64d%I64d",&n,&m,&k))
{
w=n-m;
t=n-k*w;
if(t<=0)
{
printf("%I64d\n",(n-w)%mod);
continue;
}
ans=(k-1)*w%mod;
t=(pow_mod(2,t/k+1)*k%mod+mod-2*k%mod+t%k%mod)%mod;//注意减时可能减为负数所以要加上mod因此听取蛙声一片
ans=(t+ans)%mod;
printf("%I64d\n",ans);
}
return 0;
}
决定以后好好打cf了。未完待续。。。。