Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator