NOI 1.11二分検索04:網線主管
テーマの出所:http://noi.openjudge.cn/ch0111/04/?lang=zh_CN
04:ネットワーク管理者
説明
仙境の住民たちはプログラム設計区域試合を開催することにした.審判委員会は完全にボランティアで構成され、史上最も公正な試合を組織すると約束した.彼らは選手のパソコンを星型トポロジーで接続し、単一のセンターサーバにすべて接続することにした.この完全公正な試合を組織するために、審判委員会の議長はすべての選手のパソコンをサーバーの周りに等間隔に置くことを提案した.
ネットワークケーブルを購入するために、裁判委員会は現地のネットワークソリューションプロバイダに連絡し、一定数の等長ネットワークケーブルを提供することを要求した.審判委員会は、テニスのラインが長ければ長いほど、選手たちの距離ができるだけ遠くなることを望んでいる.
同社のネットワークリーダーはこの任務を引き受けた.彼は在庫の各網線の長さ(正確にセンチメートルまで)を知っていて、必要な網線の長さ(正確にセンチメートルまで)を教えてくれれば、網線の切断を完成することができます.しかし、今回は、必要なケーブルの長さが分からず、担当者を困惑させた.
ネットワークラインの責任者が最も長いネットワークラインの長さを決定し、在庫のネットワークラインをこの長さで切断するプログラムを作成する必要があります.指定された数のネットワークラインを得ることができます.
入力
最初の行には、単一のスペースで区切られた2つの整数NとKが含まれます.N(1<=N<=10000)は在庫中の網線数であり、K(1<=K<=10000)は必要な網線数である.次のN行は、1行あたりの数で、在庫内の各網線の長さ(単位:メートル)です.すべての網線の長さは少なくとも1 m、最大100 kmである.入力のすべての長さはセンチメートルまで正確で、小数点以下の2桁まで保持されます.
しゅつりょく
網線主管は在庫の網線から指定数の網線の最長長さ(単位:メートル)を切り出すことができる.正確にセンチメートルまで、すなわち小数点以下の2桁まで保持しなければならない.少なくとも1 cmの長さの指定された数の網線が得られない場合は、「0.00」(引用符を含まない)を出力する必要があります.
サンプル入力
4 118.027.434.575.39
サンプル出力
2.00
-----------------------------------------------------
問題を解く構想.
入力したdoubleをlong longに変換してから計算します.出力するときはlong longの結果をdoubleに回して100を除くように注意してください.そうしないと、四捨五入します.
-----------------------------------------------------
コード#コード#
04:ネットワーク管理者
説明
仙境の住民たちはプログラム設計区域試合を開催することにした.審判委員会は完全にボランティアで構成され、史上最も公正な試合を組織すると約束した.彼らは選手のパソコンを星型トポロジーで接続し、単一のセンターサーバにすべて接続することにした.この完全公正な試合を組織するために、審判委員会の議長はすべての選手のパソコンをサーバーの周りに等間隔に置くことを提案した.
ネットワークケーブルを購入するために、裁判委員会は現地のネットワークソリューションプロバイダに連絡し、一定数の等長ネットワークケーブルを提供することを要求した.審判委員会は、テニスのラインが長ければ長いほど、選手たちの距離ができるだけ遠くなることを望んでいる.
同社のネットワークリーダーはこの任務を引き受けた.彼は在庫の各網線の長さ(正確にセンチメートルまで)を知っていて、必要な網線の長さ(正確にセンチメートルまで)を教えてくれれば、網線の切断を完成することができます.しかし、今回は、必要なケーブルの長さが分からず、担当者を困惑させた.
ネットワークラインの責任者が最も長いネットワークラインの長さを決定し、在庫のネットワークラインをこの長さで切断するプログラムを作成する必要があります.指定された数のネットワークラインを得ることができます.
入力
最初の行には、単一のスペースで区切られた2つの整数NとKが含まれます.N(1<=N<=10000)は在庫中の網線数であり、K(1<=K<=10000)は必要な網線数である.次のN行は、1行あたりの数で、在庫内の各網線の長さ(単位:メートル)です.すべての網線の長さは少なくとも1 m、最大100 kmである.入力のすべての長さはセンチメートルまで正確で、小数点以下の2桁まで保持されます.
しゅつりょく
網線主管は在庫の網線から指定数の網線の最長長さ(単位:メートル)を切り出すことができる.正確にセンチメートルまで、すなわち小数点以下の2桁まで保持しなければならない.少なくとも1 cmの長さの指定された数の網線が得られない場合は、「0.00」(引用符を含まない)を出力する必要があります.
サンプル入力
4 118.027.434.575.39
サンプル出力
2.00
-----------------------------------------------------
問題を解く構想.
入力したdoubleをlong longに変換してから計算します.出力するときはlong longの結果をdoubleに回して100を除くように注意してください.そうしないと、四捨五入します.
-----------------------------------------------------
コード#コード#
//04:
// : 1000ms : 65536kB
//
// 。 , 。 , 。 , 。
//
// , , 。 , 。
//
// 。 ( ), ( ), 。 , , , 。
//
// , , , 。
//
//
// N K, 。N(1 <= N <= 10000) ,K(1 <= K <= 10000) 。
// N , , ( : )。 1m, 100km。 , 。
//
// ( : )。 , 。
// 1cm , “0.00”( )。
//
//4 11
//8.02
//7.43
//4.57
//5.39
//
//2.00
#include
#include
#include
using namespace std;
const int MAX = 10001;
int n,k;
long long L[MAX];
bool judge(long long len)
{
long long cnt = 0,i;
for (i=0; i=k;
}
long long binary(long long left, long long right)
{
if (!judge(1))
{
return 0;
}
if (left==right)
{
return left;
}
if (left==right-1)
{
if (judge(right))
{
return right;
}
else
{
return left;
}
}
long long mid = (left+right)/2;
if (judge(mid))
{
binary(mid,right);
}
else
{
binary(left,mid-1);
}
}
int main()
{
#ifndef ONLINE_JUDGE
ifstream fin("0111_04.txt");
fin >> n >> k;
float tmp = 0;
int i = 0;
long long mymax = 0;
for (i=0; i> tmp;
L[i] = (long long) 100*tmp;
if (L[i]>mymax)
{
mymax = L[i];
}
}
fin.close();
long long ans = binary(1,mymax);
if (ans!=0)
{
printf("%.2f",((float)ans)/100); // y.xx
}
else
{
cout << "0.00";
}
return 0;
#endif
#ifdef ONLINE_JUDGE
cin >> n >> k;
double tmp = 0;
int i = 0;
long long mymax = 0;
for (i=0; i> tmp;
L[i] = (long long) 100*tmp;
if (L[i]>mymax)
{
mymax = L[i];
}
}
long long ans = binary(1,mymax);
//printf("%.2lf",((double)(ans/100)));
if (ans!=0)
{
printf("%.2lf",((double)ans)/100);
}
else
{
cout << "0.00";
}
return 0;
#endif
}