欲張り小結[欲張り特集16題]
13218 ワード
転載は出典を明記してください、ありがとうございますhttp://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
自分で開いたテーマは、合宿チームの夏休み合宿に使われている.テーマの出所はすでに与えられている.
![贪心小结 [贪心专题16题]_第1张图片](https://s1.md5.ltd/image/004b7eb774cb546e6ff72a3c2f0f0618.jpg)
1001
一部のリュックサックの問題.優先的に選択性価格比が高い場合は、単位価格をソートし、条件が満たされるまで順次選択します.
1002
交差していない区間は同時に行うことができます.では、必要な回数は、ある点が通過する最大回数です.
1003
貪欲な思想、先に6*6を放して、格子はすでにすべていっぱいになって、それから5*5を放して、残りの空間は1*1を放して、それから4*4を放して、残りの空間は2*2を放して、それから1*1を放して、それから3*3を放して、同じように残りの空間を処理して、最後に2*2を考えて、1*1.
1004
いいテーマですね.暴力は解けますが、面白くありません.法則並べ替えの後、iが0−(pos−1)およびjがpos−nをとると、iとjの差は必然的にa[pos]−a[pos−1]を含むことが分かった.
ではa[pos]-a[pos-1]の出現回数はi*(n-i)である.
1005
2つのキーワードで小さいものから大きいものまで並べ替え、その後を巡ります.
1006
一人一人の手にはm枚のカードがあり、n人があり、カードの数字はそれぞれ1-n*mで、互いに等しくない.
勝つ最小の情況はきっと自分で大きいことを出して、他の人は大きいことがあって、肯定的に抑えて、さもなくば他の人は最小を出します.
毎回最大のカードを選んで出して、もし他の人が大きなカードがあれば、負けて、さもなくば他の人は最小のカードを出します.シミュレーションは不要で、大きいものから小さいものまで一度遍歴します.もしあるカードがあれば、私が勝つことができることを説明して、+1、もしなければ、他の人が私より一度大きくなることができることを説明して、-1.
1007
すべての帯域幅を離散化します.
最小帯域幅として帯域幅を列挙する.次に、各グループで最小帯域幅を満たし、価格が最も低いものを選択します.
したがって、各グループについて価格の増加順に並べ替えます.低価格を優先する.
1008
自転車で学校へ行きます.時間が負の車は考えなくてもいいです.追いつけないか、追いつくのが一番速いわけではありませんから.そして各車の所要時間を求め、最小値を求める.
1009
同じように価値の減少に基づいてソートし、まず価値の高いものを満たし、日付はできるだけ後にします.
1010
終了時間でソートし、順番に巡回します.
1011
欲張りは、毎回価値の高いものを優先し、できるだけ時間が後になるようにします.flag配列でタグ付けし、ある日利用されているかどうか、すでに利用されている場合は、前を巡ります.
1012
島ごとに1つの区間が存在し、区間内の任意の位置に建てられたレーダーが島を覆うことができる.これによりいくつかの区間が形成される.各区間を左から右に巡回するには、できるだけ右端を選択し、最も多くの区間を満たすことができます.サブ区間を処理できます.あるいは遍歴中にサブ区間に遭遇した場合は,できるだけサブ区間の右端をとる.
1013
池ごとに、左から右に順番に板を置きます.
1014
黒い本の例題.まず歩いた湖の数Xを列挙すると、1からXまで歩いて、道にかかる時間を算出することができます.毎回魚が一番多い湖を選んで釣りをするのは、湖ごとに、いつでも魚の数はこの湖で釣りをする回数と関係があるので、総回数とは関係ありません.だからこれが一番いいです.
1015
経典は貪欲で、詳しく見ますhttp://blog.csdn.net/acm_cxlove/article/details/7720218
1016
必ずすべての品物を買って、価値の高いものを順番に選んで、割引の品物の価格も高いです.
自分で開いたテーマは、合宿チームの夏休み合宿に使われている.テーマの出所はすでに与えられている.
![贪心小结 [贪心专题16题]_第1张图片](https://img.md5.com/image/info8/407c31bd01084dff8db35b2a91b896a5.jpg)
1001
一部のリュックサックの問題.優先的に選択性価格比が高い場合は、単位価格をソートし、条件が満たされるまで順次選択します.
#include
#include
#include
#include
using namespace std;
struct Node{
int j,f;
double p;
}a[1000];
int n,m;
bool cmp(Node n1,Node n2){
return n1.p>n2.p;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&(n!=-1&&m!=-1)){
for(int i=0;i=n){
if(a[i].f+tmp==n)
ans+=a[i].j;
else
ans+=a[i].p*(n-tmp);
break;
}
else{
ans+=a[i].j;
tmp+=a[i].f;
}
}
printf("%.3f
",ans);
}
return 0;
} 1002
交差していない区間は同時に行うことができます.では、必要な回数は、ある点が通過する最大回数です.
#include
#include
#include
#include
using namespace std;
int t,n,x,y,a[205];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(a,0,sizeof(a));
while(n--){
scanf("%d%d",&x,&y);
if(x>y)
swap(x,y);
for(int i=(x+1)/2;i<=(y+1)/2;i++)
a[i]++;
}
int ans=0;
for(int i=1;i<=200;i++)
ans=max(ans,a[i]);
printf("%d
",ans*10);
}
return 0;
} 1003
貪欲な思想、先に6*6を放して、格子はすでにすべていっぱいになって、それから5*5を放して、残りの空間は1*1を放して、それから4*4を放して、残りの空間は2*2を放して、それから1*1を放して、それから3*3を放して、同じように残りの空間を処理して、最後に2*2を考えて、1*1.
#include
#include
#include
using namespace std;
int a,b,c,d,e,f;
int main(){
int u[4]={0,5,3,1};
while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f)&&a+b+c+d+e+f){
int ans=d+e+f+(c+3)/4;
int x=d*5+u[c%4];
if(b>=x)
ans+=(b-x+8)/9;
int y=36*ans-36*f-25*e-16*d-9*c-4*b;
if(a>y)
ans+=(a-y+35)/36;
printf("%d
",ans);
}
return 0;
} 1004
いいテーマですね.暴力は解けますが、面白くありません.法則並べ替えの後、iが0−(pos−1)およびjがpos−nをとると、iとjの差は必然的にa[pos]−a[pos−1]を含むことが分かった.
ではa[pos]-a[pos-1]の出現回数はi*(n-i)である.
#include
#include
#include
#include
using namespace std;
int a[10000],n;
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i 1005
2つのキーワードで小さいものから大きいものまで並べ替え、その後を巡ります.
#include
#include
#include
#include
#include
using namespace std;
struct Node{
int l,r;
}a[5000];
int n;
bool cmp(Node n1,Node n2){
return n1.l!=n2.l?n1.l=L&&a[j].r>=R&&flag[j]==false){
L=a[j].l;
R=a[j].r;
flag[j]=true;
}
}
printf("%d
",ans);
}
return 0;
} 1006
一人一人の手にはm枚のカードがあり、n人があり、カードの数字はそれぞれ1-n*mで、互いに等しくない.
勝つ最小の情況はきっと自分で大きいことを出して、他の人は大きいことがあって、肯定的に抑えて、さもなくば他の人は最小を出します.
毎回最大のカードを選んで出して、もし他の人が大きなカードがあれば、負けて、さもなくば他の人は最小のカードを出します.シミュレーションは不要で、大きいものから小さいものまで一度遍歴します.もしあるカードがあれば、私が勝つことができることを説明して、+1、もしなければ、他の人が私より一度大きくなることができることを説明して、-1.
#include
#include
#include
#include
#include
using namespace std;
int a[1005],n,m,k,cas=0;
bool flag[1005];
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&n+m){
memset(flag,false,sizeof(flag));
for(int i=0;i0;i--)
if(flag[i]){
tmp++;
ans=max(ans,tmp);
}
else
tmp--;
printf("Case %d: %d
",++cas,ans);
}
return 0;
} 1007
すべての帯域幅を離散化します.
最小帯域幅として帯域幅を列挙する.次に、各グループで最小帯域幅を満たし、価格が最も低いものを選択します.
したがって、各グループについて価格の増加順に並べ替えます.低価格を優先する.
#include
#include
#include
#include
#include
using namespace std;
struct Node{
int b,p;
}a[400][400];
int t,m[400],B[160000],cnt,n;
bool cmp(Node n1,Node n2){
return n1.p=B[k])
break;
if(j==m[i]){
flag=0;
break;
}
ptmp+=a[i][j].p;
}
if(flag)
ans=max(ans,B[k]*1.0/ptmp);
}
printf("%.3f
",ans);
}
return 0;
}
1008
自転車で学校へ行きます.時間が負の車は考えなくてもいいです.追いつけないか、追いつくのが一番速いわけではありませんから.そして各車の所要時間を求め、最小値を求める.
#include
#include
#include
#include
#include
using namespace std;
struct Node {
int v,t,need;
}a[10000];
int n;
int main(){
while(scanf("%d",&n)!=EOF&&n){
for(int i=0;i 1009
同じように価値の減少に基づいてソートし、まず価値の高いものを満たし、日付はできるだけ後にします.
#include
#include
#include
#include
#include
using namespace std;
struct Node{
int d,p;
}a[1000];
bool cmp(Node n1,Node n2){
return n1.p>n2.p;
}
int n,t;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i=1;j--)
if(flag[j]==false){
flag[j]=true;
break;
}
if(j==0)
ans+=a[i].p;
}
printf("%d
",ans);
}
return 0;
} 1010
終了時間でソートし、順番に巡回します.
#include
#include
#include
#include
#include
using namespace std;
struct Node{
int l,r;
}a[100];
int n;
bool cmp(Node n1,Node n2){
return n1.r!=n2.r?n1.rn2.l;
}
int main(){
while(scanf("%d",&n)!=EOF&&n){
for(int i=0;i=a[k].r){
ans++;
k=i;
}
printf("%d
",ans);
}
return 0;
}
1011
欲張りは、毎回価値の高いものを優先し、できるだけ時間が後になるようにします.flag配列でタグ付けし、ある日利用されているかどうか、すでに利用されている場合は、前を巡ります.
#include
#include
#include
#include
using namespace std;
struct Node{
int p,d;
}a[10000];
bool cmp(Node n1,Node n2){
return n1.p>n2.p;
}
int n;
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i0;t--)
if(flag[t]==false){
ans+=a[i].p;
flag[t]=true;
break;
}
printf("%d
",ans);
}
return 0;
} 1012
島ごとに1つの区間が存在し、区間内の任意の位置に建てられたレーダーが島を覆うことができる.これによりいくつかの区間が形成される.各区間を左から右に巡回するには、できるだけ右端を選択し、最も多くの区間を満たすことができます.サブ区間を処理できます.あるいは遍歴中にサブ区間に遭遇した場合は,できるだけサブ区間の右端をとる.
#include
#include
#include
#include
#include
using namespace std;
struct Node{
double l,r;
}a[1000];
int n,d;
bool cmp(Node n1,Node n2){
return n1.ld)
flag=false;
if(!flag)
continue;
a[i].l=x-sqrt((double)d*d-y*y);
a[i].r=x+sqrt((double)d*d-y*y);
}
if(!flag){
printf("Case %d: -1
",++cas);
continue;
}
sort(a,a+n,cmp);
int ans=1;
double pos=a[0].r;
for(int i=1;ipos){
pos=a[i].r;
ans++;
}
else if(a[i].r 1013
池ごとに、左から右に順番に板を置きます.
#include
#include
#include
#include
#include
using namespace std;
int n,d;
struct Node{
int l,r;
}a[10000];
bool cmp(Node n1,Node n2){
return n1.lpos){
ans+=(a[i].r-a[i].l+d-1)/d;
pos=(a[i].r-a[i].l+d-1)/d*d+a[i].l;
}
else if(a[i].r>pos){
ans+=(a[i].r-pos+d-1)/d;
pos=(a[i].r-pos+d-1)/d*d+pos;
}
}
printf("%d
",ans);
}
return 0;
} 1014
黒い本の例題.まず歩いた湖の数Xを列挙すると、1からXまで歩いて、道にかかる時間を算出することができます.毎回魚が一番多い湖を選んで釣りをするのは、湖ごとに、いつでも魚の数はこの湖で釣りをする回数と関係があるので、総回数とは関係ありません.だからこれが一番いいです.
#include
#include
#include
using namespace std;
int main()
{
int n,h,f[30],d[30],t[30],Case=0;
while(scanf("%d",&n),n>0)
{
if(Case!=0) printf("
");
Case++;
scanf("%d",&h);
h=h*60;
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
for(int i=1;i<=n;i++)
scanf("%d",&d[i]);
t[1]=0;
for(int i=1;i<=n-1;i++)
{
int a;
scanf("%d",&a);
t[i+1]=t[i]+a*5;
}
int fish=0;
int f_temp[30];
int spe[30];
int spe_temp[30];
int tt;
for(int i=1;i<=n;i++)
spe[i]=-1;
for(int i=1;i<=n;i++)
{
int sum=0;
tt=h-t[i];
for(int j=1;j<=n;j++)
f_temp[j]=f[j];
memset(spe_temp,0,sizeof(spe_temp));
while(tt>=5)
{
int mmax=0,maxj=-1;
for(int j=1;j<=i;j++)
{
if(f_temp[j]>mmax)
{
mmax=f_temp[j];
maxj=j;
}
}
if(maxj==-1)
break;
tt=tt-5;
spe_temp[maxj]++;
sum+=f_temp[maxj];
f_temp[maxj]=f_temp[maxj]-d[maxj];
}
if(sum>fish)
{
fish=sum;
for(int j=1;j<=n;j++)
spe[j]=spe_temp[j];
spe[1]+=tt/5;
}
else if(sum==fish)
{
bool flag=false;
for(int j=1;j<=n;j++)
if(spe[j]spe_temp[j])
break;
if(flag)
{
fish=sum;
for(int j=1;j<=n;j++)
spe[j]=spe_temp[j];
spe[1]+=tt/5;
}
}
}
for(int i=1;i 1015
経典は貪欲で、詳しく見ますhttp://blog.csdn.net/acm_cxlove/article/details/7720218
1016
必ずすべての品物を買って、価値の高いものを順番に選んで、割引の品物の価格も高いです.
#include
#include
#include
#include
#include
using namespace std;
int t,n,a[20000];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i=0;i-=3)
ans+=a[i];
printf("%d
",ans);
}
return 0;
}