标签存档：水题

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
给出一个24小时制的时间，让你输出它的前45分钟时多少。
【算法分析】
类a-b problems
【其它】
。。。其实我不想写的，但是为了完整性，还是写一下。。。
【CODE】
#include int main(){
int H,M;
scanf("%d%d",&H,&M);
M-=45;
if (M<0){M+=60; H--;}
if (H<0) H+=24;
printf("%d %dn",H,M);
}

【BOI链接】http://www.ut.ee/boi/
【题目大意】
按顺序给出n<=20000个箱子，他们的尺寸m<=1000。
求一个最大的k，使得前k个和第k+1个到2*k个箱子之间能一一匹配。
能匹配的定义是i∈[1,k] 且 j∈[k+1,2*k] 同时Size[i]【算法分析】
因为m<=1000，开一个1000的桶，然后从k从n/2开始枚举下来，维护一下。
由于O(nm)都不会超时，直接每次都暴力判断就好了。
【CODE】
#include #include #include int a[20001],t1[1001],t2[1001];

bool flag(){
int num1=0,num2=0,i;
for (i=1;i<=m;i++){
if (num1 num1+=t1[i];
num2+=t2[i];
if (num1 }
return true;
}

int main(){
int i,k,ans=0;
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
freopen("bins.in","r",stdin);
freopen("bins.out","w",stdout);
scanf("%d%d",&m,&n);
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
k=n/2;
for (i=1;i<=k;i++) t1[a[i]]++;
for (i=k+1;i<=2*k;i++) t2[a[i]]++;
for (k=n/2;k>=0;k–){
if (flag()){
ans=k;
break;
}
if (!k) break;
t1[a[k]]–;
t2[a[k]]++;
t2[a[2*k]]–;
t2[a[2*k-1]]–;
}
printf("%dn",ans);
}

【算法分析】
排序，然后判断就可以。
对于每只蚂蚁，我们只考虑他什么时候能追上前面那只蚂蚁就可以，因为被追上与之是对应的。
所以我们要尽量让后面那只蚂蚁难追上前面那只蚂蚁。
所以我们排序即可。
【CODE】
#include #include #include #include #include using namespace std;
const double pi=3.141592653589793238462643383279502884197169399375;
int n;
int a[100005];
double r;

void input(){
scanf("%d %lf",&n,&r);
for (int i=0;i scanf("%d",&a[i]);
r=2*r*pi/n;
}

void solve(){
double ans=1e50;
for (int i=1;i if (a[i]!=a[i-1] && r/(a[i]-a[i-1]) ans=r/(a[i]-a[i-1]);
if (ans==1e50) printf("Infn");
else printf("%.3lfn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
input();
sort(a,a+n);
solve();
}
}

【题目大意】

给定一个数组A[i]，1<=a[i]<=10000

求把它分成M份，每份的和不超过一个值K。

问K最小是多少？

【算法分析】

注意到A[i]都是正数，所以我们可以二分答案，然后线性贪心判断即可。

如果A[i]存在负数的话，这个算法就不正确了。

【其它】

1WA，1A。悲剧，忘了删文件。

另外一开始想了挺久的。。。最主要是读题不够仔细，没看到那个A[i]>=1

【CODE】

#include #include #include typedef long long LL;
int m,n;
int a[101111],Max=0;

bool flag(LL limit){
    int num=1;
    LL sum=a[1];
    for (int i=2;i<=n;i++)
      if (sum+a[i]>limit){
          num++;
          sum=a[i];
      }
      else sum+=a[i];
    if (num>m) return false;
    return true;
}   

int main(){
    scanf("%d%d",&n,&m);
    LL sum=0;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if (a[i]>Max) Max=a[i];
        sum+=a[i];
    }   
    LL l=Max,r=sum,mid;
    while (l        mid=(l+r)/2;
        if (flag(mid)) r=mid;
                  else l=mid+1;
    }
    printf("%lldn",l);
}   

【题目大意】

给偶数个人分组，使得组员的体重相差值之和最小。

【算法分析】

该次月赛的送分题。

显然，排序以后按顺序两两匹配即可。

证明：

若a<=b<=c<=d

即证明：d-c+b-a<=d-a+c-b

推导出：b<=c

符合条件，所以得证。

【CODE】

#include #include #include #include #include using namespace std;
struct datatype{int d,pos;}a[11111];
int n;

inline bool cmp(datatype x,datatype y){
    return x.d}   

int main(){
    int tc=0;
    while (scanf("%d",&n)!=EOF){
        tc++;
        if (tc!=1) printf("n");
        for (int i=1;i<=n;i++) scanf("%d",&a[i].d);
        for (int i=1;i<=n;i++) a[i].pos=i;
        sort(&a[1],&a[n+1],cmp);
        for (int i=1;i          printf("%d %dn",a[i].pos,a[i+1].pos);
    }   
}