求助,80分第三个点TLE

P3613 【深基15.例2】寄包柜

Anduin9527 @ 2021-04-03 12:23:47

呜呜呜

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef struct ListNode *List;
struct ListNode
{
  int i;
  int j;
  ll k;
  List Next;
};
List L = new ListNode;
List AppendNode(int i, int j, int k)
{

  if (k != 0 || L==nullptr)
  {
    List New, Pre = L;
    if (L == nullptr||L->k==0) //L为空
    {
      New = new ListNode;
      New->i = i;
      New->j = j;
      New->k = k;
      New->Next = nullptr;
      return New;
    }
    else //L不为空则尾插
    {
      while (Pre->Next != nullptr)
        Pre = Pre->Next;
      New = new ListNode;
      New->i = i;
      New->j = j;
      New->k = k;
      New->Next = nullptr;
      Pre->Next = New;
      return L;
    }
  }
  else
  {
    List Pre = L, Temp = L;
    while (!(Temp->i == i && Temp->j == j))
    {
      Pre = Temp; //Pre为要删除结点的前一个结点
      Temp = Temp->Next;
    }

    if (Pre == Temp) //坑:说明此时只有一个结点L
      L->k = 0;
    else
    {
      Pre->Next = Temp->Next;
      free(Temp);
    }
    return L;
  }
}
void FindNode(int i, int j)
{

  List Temp = L;
  ll ans;
  while (Temp->Next != nullptr)
  {
    if (Temp->i == i && Temp->j == j)
      ans = Temp->k; //坑点:存在一个柜子两次放置物品的可能,所以取更新的k作为答案
    Temp = Temp->Next;
    //最好的方式当然是逆序遍历链表但是,懒得写双向就这样吧
  }
  if (Temp->i == i && Temp->j == j)
    ans = Temp->k; //检查尾节点
  printf("%lld\n", ans);
}
int main()
{
  L = nullptr;
  int n, q;
  cin >> n >> q;
  while (q--)
  {
    int i, j, k, type;
    cin >> type;
    if (type == 1)
    {
      cin >> i >> j >> k;
      L = AppendNode(i, j, k);
    }
    else
    {
      cin >> i >> j;
      FindNode(i, j);
    }
  }
  return 0;
}

by Aslf_Ek @ 2021-07-26 22:49:17

我的方法和你差不多,我是用队列做的,暴力找柜子格子,然后再做决策,也TLE了。我觉的可以用哈希?


by woshixjk @ 2021-08-12 19:09:00

开O2优化,我一开始也是第三个点TLE,开O2之后过了,再不行就加上快读


|