UVA2322和2.2的一些思考-木棍时间问题-白红宇

UVA2322和2.2的一些思考-木棍时间问题

阅读量：4143 次

发布时间：2019-05-25

本文共 4055 字，大约阅读时间需要 13 分钟。

题目链接：https://vjudge.net/contest/210716#problem/H

==========一些思考===========

======为什么我的会超时呢=====

（其实我只要不看手机，真的效率就就很可怕了！）

（好的咯...别辜负她们的期望呀!）

（别看手机！直到40分钟响了未知，然后去洗了衣服或者收拾一下再看手机，你不会失去什么的！！！）

我的思想是，是按照这个比较的没错，然后把数组复制一下，每次都挑选出来符合条件的

但是在面对数据量非常大的时候，就很吃亏了，每次要比较，要转移一次，再转移一次

看网上这个人的代码的思想呢：

比较奇特，对于每一个n

for(i=1;i<n;i++)

for(j=1;j<rnt;j++)【画重点，rnt】

if(长和宽*2) //不满足条件的话

flag=0;

一直都是正序列的，

查找是2n吧这样。。还是不到n方？ n方吧两重

if(flag==0)

rnt=tmp[i];

也就是一个数组存很多个东西

以rnt的坐标为基准的几组，在里面卡的好好儿的

以rnt和j为坐标的几组，如果新的i这几组的等价关系都不满足的话，把它作为新的，再去存一次。

rnt显然必须要是最大的，如果不是的话打死（划掉）存上。

此外，只是用了sort一次，感觉优先队列每次插入的话更麻烦，每次都要排序的话很容易超时的吧。

用了sort是确保最大优秀的吧。

不然的话，岂不是只能看随机分配的了。

=====附代码========

ac代码

#include 
   
      #include 
    
       #include 
     
        using namespace std;const int N = 5005;struct stick {	int len;	int wei;}tmp[N], rec[N];bool cmp(const stick& a, const stick& b) {	if (a.len != b.len)		return a.len < b.len;	else		return a.wei < b.wei;}int main() {	int cas, n, cnt, begin;	scanf_s("%d", &cas);	while (cas--) {		cnt = 0;		memset(tmp, 0, sizeof(tmp));		memset(rec, 0, sizeof(rec));		scanf_s("%d", &n);		for (int i = 0; i < n; i++)			scanf_s("%d %d", &tmp[i].len, &tmp[i].wei);		sort(tmp, tmp + n, cmp);//没用优先队列，而是用的这个。。会简单不少吗		for (int i = 0; i < n; i++) {			int flag = 1;			for (int j = 0; j < cnt; j++) {				if (tmp[i].len >= rec[j].len && tmp[i].wei >= rec[j].wei) {     					rec[j] = tmp[i];					flag = 0;					break;				}			}			if (flag)   rec[cnt++] = tmp[i];		}		printf("%d\n", cnt);	}	return 0;}

以及我自己超时了的。。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;//PLease!!!//（起码是）在你的事情做完之前，不要理他们。//不要！！！！！！// 2.4基本都关门了也是xxx回来了考虑 和小可爱吃饭吧// 啊啊啊啊啊啊啊111!!!!// 哇哈哈哈先让我笑死吧，果然坚持不下去的时候逼迫自己一把会发现环境真的是太重要了对我而言哇哈哈哈// 哇哈哈哈哈.,, 不要理他们（对）////(if ever)回去写题解，电脑随身携带，或者回去重新打一遍哇哈哈哈//struct stick{	int len;	int width;	//stick(int len = 0, int width = 0) :		//len(len),width(width){}		bool operator<( const stick&b)const	{		return this->len
       
        q;	priority_queue
        
         q2; int m; cin >> m; while (m--){ int n; cin >> n; for (int i = 0; i < n; i++) { cin >> sticks[i].len >> sticks[i].width; //输入了这两个 //怎么一起push吗 嗯 q.push(sticks[i]); } //很好，已经完成了数据的初始化 //接下来的数据是按照len长度排序的 int result = 0; while (!q.empty()) { //stick temp1 = q.top(); //q.pop(); //stick temp2 = q.top(); //now that we have known that q/ stick temp1 = q.top(); q.pop(); while (!q.empty()){ // 先把第一个取出来，再跟第一个比较，直到找到第一个的为止。 if (q.top().width > temp1.width)//不乖的宝宝都给我踢出去 { q2.push(q.top()); q.pop(); } else// 乖宝宝，直接踢出去 q.pop(); } //然后，从q2那里转移过来，还是优先队列。 while (!q2.empty()) { q.push(q2.top()); q2.pop(); } result++; // “我已经把你们按照len排起来了，width不这样我也没办法 //result++; //q.push(temp2); //else // else... else...... else //********************that's why i love it do yoyu forget???? //【pop 和push的敏感啊啊啊啊啊啊】。 //每次都pop出来一个吗》？不知 // q.push(temp2); } cout << result << endl; } return 0;}