Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 最简单的算法 ^_^, 先除2直到不划算或者不行为止

Posted by wm3418925 at 2015-08-24 17:20:41 on Problem 1907
```#include <stdio.h>
#include <string.h>

typedef struct
{
int v;
int p1, p2;
char name[17];
}my_info;
int my_cmp(void * a, void * b)
{
my_info * x = (my_info *)a;
my_info * y = (my_info *)b;
if (x->v < y->v)
return -1;
else if (x->v > y->v)
return 1;
else
{
return strcmp(x->name, y->name);
}
}

int n, m, count;
my_info l[100];

int div_d(int a, int b)
{
int d = a/b;
if (d * b == a)
return d;
else
return d+1;
}
void solve()
{
int i;
int min_n;

for (i=0; i<count; ++i)
{
my_info * t = &(l[i]);
int c = n;

if (t->p1 <= 0)
{
t->v = 0;
continue;
}

min_n = div_d(2*t->p2, t->p1);
t->v = 0;

while (c >= min_n && (c>>1) >= m)
{
c >>= 1;
t->v += t->p2;
}

t->v += (c-m)*t->p1;
}

qsort(l, count, sizeof(my_info), my_cmp);
}

void print_result()
{
int i;

for (i=0; i<count; ++i)
{
my_info * t = &(l[i]);
printf("%s %d\n", t->name, t->v);
}
}

int main()
{
int cases, i, j;
char line[256];

scanf("%d\n", &cases);

for (i=0; i<cases; ++i)
{
scanf("%d %d %d\n", &n, &m, &count);

for (j=0; j<count; ++j)
{
char * tmp_p;
gets(line);
tmp_p=strchr(line, ':');
memcpy(l[j].name, line, tmp_p-line);
l[j].name[tmp_p-line] = '\0';

sscanf(tmp_p+1, "%d,%d", &l[j].p1, &l[j].p2);
}

solve();

printf("Case %d\n", i+1);
print_result();
}

return 0;
}```

Followed by: