关于奶牛的几道水题

　　在COGS上进行了努力寻找之后发现了这几道题实际上是[NOIP2010冲刺十二]的题(虽然并不知道是什么东西) 　　这道题实在是太水了，以至于我不去写个解题报告都觉得对不起这几道题。　　http://cogs.pro/cogs/problem/problem.php?pid=1211 　　首先是第一道题目: 奶牛晒衣服 　　这道题目实际上是很久很久以前就水过的题目(实际上这三道题目都是水过的) 　　实际上就是最基本的贪心的思想。首先，我们所需要的仅仅只是略微的使用一下优先队列(STL里的)priority_queue就可以了。(不过实际上也可以用二分答案做) 　　也就是我们把所有衣服的湿度都加入到优先队列中，然后不断的对队列中最大的数进行烘干，然后就没有什么了，直接上代码就行了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


#include <cstdio>
#include <cstring>
#include <queue> 
#include <algorithm>
using namespace std;
priority_queue<int>q;
int n,a,b;
void read()
{
    scanf("%d%d%d",&n,&a,&b);
    int w;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&w);
        q.push(w);//将湿度入队； 
    }
    int sum=0;
    int t=0;
    while(!q.empty())//如果队列不为空，即还有衣服没晾干； 
    {
        int k=q.top();
        if(k<=sum){
            printf("%d",t);
            return;
        }//如果无需烘干，即当前的自然晒干的湿度的总和>衣服的湿度，直接打印； 
        else{//需要烘干机； 
            q.pop(); 
            k-=b;//烘干机操作后的湿度； 
            sum+=a;//自然晒干的湿度的总和等于这一次操作之前适度的总和加这一次的晒干的湿度； 
            t++;//时间加一； 
            q.push(k);//将k再次入队判断（因为k还没有晾干所以还需要更多的时间） 
        }
    }
    printf("%d",t);
}
int main()
{
 #ifdef LOCAL
        freopen("dry.in","r",stdin);
        freopen("dry.out","w",stdout);
    #endif //LOCAL
    read();
}

　　紧接着就是第二道题目:奶牛排队 　　对于这道题目,蒟蒻根本无法想出正解。(而吴锛锛同学则告诉我他使用的是暴力做法，而且还AC了！而我对此表示毫无办法，就当我什么都没有听到吧) 　　然后进行了思考之后觉得应该是用　　法一：单调栈预处理然后枚举，针对n很大但单调长度很短的数据增加优化（可行的最大长度（即枚举时只枚举到该点之后的最大数，如果还有坑数据，再预处理该段长度，然后枚举时判断是否需要枚举（如果最长长度都小于ans还枚举干嘛））） code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
struct statype
{
 int bhei,bpos,ahei,apos;
}sta[100010];
 
int top=-1;
 
int main(void)
{
 #ifdef LOCAL
  freopen("tahort.in","r",stdin);
  freopen("tahort.out","w",stdout);
 #endif //LOCAL 
 int i,n,ans=0;
 cin>>n;
 for (i=1;i<=n;i++)
 {
  top++;
  cin>>sta[top].bhei;
  sta[top].ahei=sta[top].bhei;
  sta[top].bpos=i;
  sta[top].apos=i;
  while (sta[top].bhei>sta[top-1].bhei&&top>=1)
  {
   if (sta[top].ahei>sta[top-1].ahei)
   {
    sta[top].ahei=sta[top-1].ahei;
    sta[top].apos=sta[top-1].apos;
   }
   sta[top-1]=sta[top];
   sta[top].bhei=0;
   sta[top].bpos=0;
   sta[top].apos=0;
   top--;
  }
  if (ans<sta[top].bpos-sta[top].apos+1)
   ans=sta[top].bpos-sta[top].apos+1;
 }
 if (ans==1)
  ans=0;
 cout<<ans<<endl;
 return(0);
}

　　　　法二：先用st或线段树求出区间最大和最小,然后深搜或者广搜都行,推荐深搜,好写.每次搜加两个关键字,分别为区间的左端点l和右端点r,然后用区间最大最小求出他们之间的最大值和最小值的下标ml,mr.如果mr>ml说明区间合法,维护ans,如果ml>=mr说明区间不合法,需要交换.最后就是将区间裂成(l,ml) (ml+1,mr-1) (mr,r),继续搜. code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78


#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=100010;
int INF,N,Num[MAXN],ans=0;
 
class SegTree
{
public:
 int l,r,mid,maxp,minp; SegTree *lc,*rc;
 void clear(){maxp=0,minp=0,lc=NULL,rc=NULL;}
}*Root;
 
inline void init()
{
 scanf("%d\n",&N);
 for(int i=1;i<=N;i++) 
  scanf("%d",&Num[i]);
 INF=*max_element(Num+1,Num+1+N);INF++;
 Root=new SegTree;
}
 
void build(SegTree *pnt,int l,int r)
{
 pnt->l=l,pnt->r=r,pnt->mid=(l+r)/2;
 if(l==r) {pnt->maxp=l,pnt->minp=r;return;}
 pnt->lc=new SegTree; build(pnt->lc,l,pnt->mid);
 pnt->rc=new SegTree; build(pnt->rc,pnt->mid+1,r);
 if(Num[pnt->lc->maxp]>=Num[pnt->rc->maxp]) 
  pnt->maxp=pnt->lc->maxp;
  else pnt->maxp=pnt->rc->maxp;
 if(Num[pnt->rc->minp]<=Num[pnt->lc->minp])
  pnt->minp=pnt->rc->minp;
  else pnt->minp=pnt->lc->minp; 
}
 
int FindMax(SegTree *pnt,int l,int r)
{
 if(pnt->l==l&&pnt->r==r) return pnt->maxp;
 if(r<=pnt->mid) return FindMax(pnt->lc,l,r);
 if(l>=pnt->mid+1) return FindMax(pnt->rc,l,r);
 int a=FindMax(pnt->lc,l,pnt->mid);
 int b=FindMax(pnt->rc,pnt->mid+1,r);
 if(Num[a]>=Num[b]) return a;return b;
}
int FindMin(SegTree *pnt,int l,int r)
{
 if(pnt->l==l&&pnt->r==r) return pnt->minp;
 if(r<=pnt->mid) return FindMin(pnt->lc,l,r);
 if(l>=pnt->mid+1) return FindMin(pnt->rc,l,r);
 int a=FindMin(pnt->lc,l,pnt->mid);
 int b=FindMin(pnt->rc,pnt->mid+1,r);
 if(Num[b]<=Num[a]) return b;return a;
}
 
void dfs(int l,int r)
{
 if(l>=r) return;
 int big=FindMax(Root,l,r);
 int small=FindMin(Root,l,r);
 if(big>small) 
 {
  if(big-small+1>ans) ans=big-small+1;
  dfs(l,small); dfs(big,r); return;
 }
 if(big==small) return;
 dfs(l,big); dfs(big+1,small-1); dfs(small+1,r);
}
 
int main()
{
 freopen("tahort.in","r",stdin);
 freopen("tahort.out","w",stdout);
 init(); build(Root,1,N); dfs(1,N);
 printf("%d\n",ans);
 return 0;
}

　　法三：我知道一定有正解，本人太弱想不出。。。（至于暴力的解法。。我实在是没有什么话好说) 　　那么就暂且放在这里，等到那一天再说吧 (@birdy ) 　　最后就是第三道题目了:没错! 圆圈舞蹈 　　　　就是简单的模拟暴力吧，但是马老师又留了一套题，等到待会再接着写吧，先把代码贴在这里: code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include<stdio.h>
inline void read(int &x)
{
 int flag=1;
 char ch;
 while(ch=getchar(),ch<'0'||ch>'9') if(ch=='-') flag=-1;
 x=(ch^'0');
 while(ch=getchar(),ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^'0');
 x*=flag;
}
int max(int a,int b){if(a>b)return a;else return b;}
int min(int a,int b){if(a<b)return a;else return b;}
int a[300001]={0},s[300001]={0};
int cy()
{
 freopen("circlea.in","r",stdin);
 freopen("circlea.out","w",stdout);
 int n,MAX=0,sum=0,head=1,tail=1,tot=0;
 read(n);
 for(int k=1;k<=n;k++)read(a[k]),a[n+k]=a[k],tot+=a[k];
 while(tail<=n*2)
 {
  sum+=a[tail];
  while(tot-sum<sum) {sum-=a[head];head++;}
  MAX=max(MAX,min(tot-sum,sum));tail++;
 }
 printf("%d\n",MAX);
 return 0;
}
int y=cy();
int main(){;}

文章目录