m_asadpoor
جمعه 11 دی 1388, 17:51 عصر
سلام. یکی از سوال های مسابقه ACM امسال با این عنواناینطوری مطرح شده بود که یک تعداد جعبه داریم که در کنار هم روی یک میز هستند و در هر جعبه کلید جعبه های کناری ان هستند و در ابتدا در تمام جعبه ها قفل است .کلید بعضی از جعبه ها به ما داده میشود و در بعضی از جعبه ها هم الماس وجود دارد که به ما میگویند که کدام جعبه ها است .باید حداقل جعبه هایی که باید باز شود تا همه الماس ها را بدست بیاریم باید در خروجی چاپ شود.
برای حل ان این الگوریتم را به کار بردم که اول فاصله هر جعبه که کلیدش رو داریم با جعبه هایی که الماس دارند را بدست میاریم و بعد مینمم را انتخاب میکنیم و اون جعبه الماس را که باز کریم از ارایه مربوط به ان حذف میکنیم و به ارایه کلیدها اضافه میکنیم تا زمانی که ارایه الماس خالی شود. کدی که نوشتم را میبینید ولی به درستی کار نمیکنه .لطفا اگر کسی هست کمک کنه ممنون میشم .
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace Diamond
{
class Program
{
static void Main(string[] args)
{
string nmd;//string for giving input
string boxkey;//string for giving input
string boxdiamond;//string for giving input
int numbox;//number of boxes
int diamond;//number of boxes contain diamond
int numkey;//number of boxes that keys of this were given to us
string[] mixline;//use for convert string to int
string[] akey;//use for convert strin to int
string[] adiamond;//use for convert strin to int
int[] n = new int[3];
int[] k;
int[] d;
int min = 0;
int[,] distance;//distance of key to diamon
int minbox = 0;//minimum boxes that must be open
int key;
int omit =0;
do
{
int index;
nmd = Console.ReadLine();
mixline = nmd.Split(' ');
for (index = 0; index < mixline.Length; index++)
n[index]= int.Parse(mixline[index]);
numbox = n[0];
numkey = n[1];
key=n[1];
diamond = n[2];
int reapet = n[2];
k = new int[numkey];
d = new int[diamond];
boxkey = Console.ReadLine();
akey = boxkey.Split(' ');
for (index = 0; index < numkey; index++)
k[index] = int.Parse(akey[index]);
boxdiamond = Console.ReadLine();
adiamond = boxdiamond.Split(' ');
for (index = 0; index < diamond; index++)
d[index] = int.Parse(adiamond[index]);
//start
distance = new int[numkey, diamond];
int i;
int j;
int pkey=0;
int help=0;
int hmin=0;
int hkey=0;
min = Math.Abs(k[0] - d[0]);
hmin=min;
while(reapet >0)
{
for (i = 0; i < numkey; i++)
{
for (j = 0; j < diamond ; j++)
{
if (d[j].Equals(2 * numbox))
distance[i, j] = 2*numbox ;
else
distance[i, j] = Math.Abs(k[i] - d[j]);
if (distance[i, j] <min)
{
if(i<key)
pkey=pkey+1;
if (distance[i, j] == 0)
{
minbox = minbox + 1;
omit = d[j];
d[j] = 2 * numbox;
}
else
{
min = distance[i, j];
minbox = (minbox + min);
omit = d[j];
d[j] = 2 * numbox;
}
}
else if (distance[i, j].Equals(min))
{
if(i<key)
hkey=hkey+1;
help = min;
index=j;
}
else
continue;
}
}
if (help != 0 && min == hmin)
{
min = help;
pkey = hkey;
omit = d[index];
d[index] = 2 * numbox;
minbox = minbox + min;
}
int[] newarray = new int[numkey];
numkey = numkey + 1;
k.CopyTo(newarray,0);
k = new int[numkey];
newarray.CopyTo(k,0);
k[k.Length - 1] = omit;
reapet=reapet-1;
distance=new int [numkey,diamond];
}
minbox=(minbox+pkey);
Console.WriteLine(minbox);
} while (Console.ReadLine() != "0 0 0");//end of while
}//end of main
}
}
برای حل ان این الگوریتم را به کار بردم که اول فاصله هر جعبه که کلیدش رو داریم با جعبه هایی که الماس دارند را بدست میاریم و بعد مینمم را انتخاب میکنیم و اون جعبه الماس را که باز کریم از ارایه مربوط به ان حذف میکنیم و به ارایه کلیدها اضافه میکنیم تا زمانی که ارایه الماس خالی شود. کدی که نوشتم را میبینید ولی به درستی کار نمیکنه .لطفا اگر کسی هست کمک کنه ممنون میشم .
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace Diamond
{
class Program
{
static void Main(string[] args)
{
string nmd;//string for giving input
string boxkey;//string for giving input
string boxdiamond;//string for giving input
int numbox;//number of boxes
int diamond;//number of boxes contain diamond
int numkey;//number of boxes that keys of this were given to us
string[] mixline;//use for convert string to int
string[] akey;//use for convert strin to int
string[] adiamond;//use for convert strin to int
int[] n = new int[3];
int[] k;
int[] d;
int min = 0;
int[,] distance;//distance of key to diamon
int minbox = 0;//minimum boxes that must be open
int key;
int omit =0;
do
{
int index;
nmd = Console.ReadLine();
mixline = nmd.Split(' ');
for (index = 0; index < mixline.Length; index++)
n[index]= int.Parse(mixline[index]);
numbox = n[0];
numkey = n[1];
key=n[1];
diamond = n[2];
int reapet = n[2];
k = new int[numkey];
d = new int[diamond];
boxkey = Console.ReadLine();
akey = boxkey.Split(' ');
for (index = 0; index < numkey; index++)
k[index] = int.Parse(akey[index]);
boxdiamond = Console.ReadLine();
adiamond = boxdiamond.Split(' ');
for (index = 0; index < diamond; index++)
d[index] = int.Parse(adiamond[index]);
//start
distance = new int[numkey, diamond];
int i;
int j;
int pkey=0;
int help=0;
int hmin=0;
int hkey=0;
min = Math.Abs(k[0] - d[0]);
hmin=min;
while(reapet >0)
{
for (i = 0; i < numkey; i++)
{
for (j = 0; j < diamond ; j++)
{
if (d[j].Equals(2 * numbox))
distance[i, j] = 2*numbox ;
else
distance[i, j] = Math.Abs(k[i] - d[j]);
if (distance[i, j] <min)
{
if(i<key)
pkey=pkey+1;
if (distance[i, j] == 0)
{
minbox = minbox + 1;
omit = d[j];
d[j] = 2 * numbox;
}
else
{
min = distance[i, j];
minbox = (minbox + min);
omit = d[j];
d[j] = 2 * numbox;
}
}
else if (distance[i, j].Equals(min))
{
if(i<key)
hkey=hkey+1;
help = min;
index=j;
}
else
continue;
}
}
if (help != 0 && min == hmin)
{
min = help;
pkey = hkey;
omit = d[index];
d[index] = 2 * numbox;
minbox = minbox + min;
}
int[] newarray = new int[numkey];
numkey = numkey + 1;
k.CopyTo(newarray,0);
k = new int[numkey];
newarray.CopyTo(k,0);
k[k.Length - 1] = omit;
reapet=reapet-1;
distance=new int [numkey,diamond];
}
minbox=(minbox+pkey);
Console.WriteLine(minbox);
} while (Console.ReadLine() != "0 0 0");//end of while
}//end of main
}
}