2016年1月13日 星期三

[HOJ 275]LASER

HOJ生病惹QQ,因此我在這裡做了題目備份,請參考~

首先可以拿出v個發射器和接收器,產生v*(v-1)/2的能量
先求出最大的v
如果能量還是不足,假設不足remain,就再拿一組發射器和接受器,發射器放在第一個位置,接受器放在第remain+1個位置,這樣就剛好多remain個交叉了

code:


#include<cstdio>
#include<cmath>
#include<cassert>
typedef long long LL;
LL N,K;
int ANS[200000];
int main()
{
// freopen("in.txt","r",stdin);
 {int x1,x2;scanf("%lld%lld%d%d",&N,&K,&x1,&x2);}
 LL v=sqrt(K*2LL);
 if((v+1LL)*v/2LL<=K)v++;
 assert(v*(v-1LL)/2LL<=K&&(v+1LL)*v/2LL>K);
 const LL remain=K-v*(v-1LL)/2LL;
 if(remain==0LL)
 {
  for(int i=0;i<v;i++)ANS[i]=v-1-i;
  for(int i=v;i<N;i++)ANS[i]=i;
 }
 else
 {
  ANS[0]=remain;
  for(int i=1,j=v;i<=v;i++,j--)
  {
   if(j==remain)j--;
   ANS[i]=j;
  }
  for(int i=v+1;i<N;i++)ANS[i]=i;
 }
 for(int i=0;i<N;i++)
 {
  if(i)putchar(' ');
  printf("%d",ANS[i]+1);
 }
 puts("");
 return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原