【NOIPシミュレーション】プレゼントを買う苦労
4835 ワード
問題面
XさんはCさんにN件のプレゼントを选んで、顺番に买って赠りましたが、给料も小遣いもないかわいそうな子供として、M人の親切な学生が援助の手を差し伸べました.しかし、最高の借金を减らすために、XさんはOIコンテストのあなたが合理的に计画して、彼に楽にプレゼントを送ることができることを望んでいます.
30%のデータ満足:n≦10;60%のデータが満足する:n≦1000;100%のデータ満足:n≦100000
ぶんせき
明らかな二分裸問題
しかし、なぜ機械室の大物たちは60を惨めに掛け、私のような弱い鶏も見逃さないのだろうか.
序列を作った人もいれば、細かいことを書いた人もいます.私は前回尺取法(二重針)の問題を書いたとき、どのように調整しても死循で、自閉しました.
そこで今回は死ぬ前に++を多くしました.しかし、本当に頭がはっきりしていないので、ポインタはもう後ろに移動して、++は必要ありません.
太水鍋
コード#コード#
転載先:https://www.cnblogs.com/NSD-email0820/p/9909183.html
XさんはCさんにN件のプレゼントを选んで、顺番に买って赠りましたが、给料も小遣いもないかわいそうな子供として、M人の親切な学生が援助の手を差し伸べました.しかし、最高の借金を减らすために、XさんはOIコンテストのあなたが合理的に计画して、彼に楽にプレゼントを送ることができることを望んでいます.
30%のデータ満足:n≦10;60%のデータが満足する:n≦1000;100%のデータ満足:n≦100000
ぶんせき
明らかな二分裸問題
しかし、なぜ機械室の大物たちは60を惨めに掛け、私のような弱い鶏も見逃さないのだろうか.
序列を作った人もいれば、細かいことを書いた人もいます.私は前回尺取法(二重針)の問題を書いたとき、どのように調整しても死循で、自閉しました.
そこで今回は死ぬ前に++を多くしました.しかし、本当に頭がはっきりしていないので、ポインタはもう後ろに移動して、++は必要ありません.
太水鍋
コード#コード#
#include
using namespace std;
#define N 100010
int n,m,l,r,ans,mid,te;
int a[N];
template<class T>
inline void read(T &x)
{
x=0;int f=1;static char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline int check(int x)
{
int i=1,rem=m,now;
while(i<=n)
{
now=0;
while(now+a[i]<=x)now+=a[i],i++;
if(rem==0)return 0;
rem--;//i++;
}
return 1;
}
int main()
{
read(n),read(m);
for(int i=1;i<=n;i++)read(a[i]),l=max(l,a[i]);
r=1000000000;
while(l<=r)
{
mid=l+r>>1;
if(check(mid))
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}
転載先:https://www.cnblogs.com/NSD-email0820/p/9909183.html